Giải bài trực tuyến

Đây là một số kiến thức về biểu diễn số trên máy tính trước khi các bạn giải bài toán này. Với n bit, máy tính có thể biểu diễn được 2ⁿ số trong phạm vi -2^n-1..(2^n-1-1). Máy tính sử dụng các số bù 2 để biểu diễn các số âm. Trong cách biểu diễn số bù 2 có n bit thì:

• Số x ≥ 0 được biểu diễn bằng chính số x.
• Số x < 0 được biểu diễn bằng số 2ⁿ - x.

Dưới đây là bảng biểu diễn số bù 2 với 3 bit:

Ưu điểm của số bù 2 là phép cộng có thể thực hiện hoàn toàn như các số không dấu. Với x > 0, x + (-x) = 2ⁿ = 0 vì các số chỉ được biểu diễn bởi n bit. Ví dụ, xét phép cộng (-2) + 3 trong biểu diễn số bù hai 3 bit:

 110
+011
 ---
 001

Kết quả bằng 1.

Với x ≥ 0, biểu diễn số bù 2 của -x sẽ thu được bằng cách đảo toàn bộ bit của x và cộng thêm 1 đơn vị. Nói cách khác -x = (NOT x) + 1. Để chỉ ra biểu thức này đúng, ta nhận xét rằng NOT x = 2ⁿ-1-x, do đó (NOT x) + 1 = 2ⁿ-x chính là biểu diễn của số -x. Với x < 0, ta cũng có -x = (NOT x) + 1.

Trong bài toán này, bạn cần thực hiện phép nhân hai số bù hai có n bit. Kết quả trả về cũng là một số bù hai n bit. Bạn hãy thông báo lỗi nếu kết quả vượt quả phạm vi biểu diễn.

Dữ liệu

Gồm nhiều bộ test, mỗi bộ test có dạng như sau:

Dòng đầu tiên chứa số n (0 ≤ n ≤ 1024) là số bit. n=0 cho biết kết thúc dữ liệu nhập. Nếu n>0, hai dòng tiếp theo, mỗi dòng chứa một số bù hai có n bit.

Có không quá 40 bộ test.

Kết quả

Gồm nhiều dòng, mỗi dòng tương ứng với một test chứa một số bù hai với số bit tương ứng là kết quả của phép nhân hoặc chứa chuỗi 'overflow' nếu kết quả vượt qua phạm vi biểu diễn.

Ví dụ

Dữ liệu
3
110
011
4
0011
1110
0

Kết quả
overflow
1010