Binary multiplication

View as PDF

Submit solution

Points: 1.14 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
© VNOI
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Đâ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^{n}~ 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 \geq 0~ được biểu diễn bằng chính số ~x~.
  • Số ~x < 0~ được biểu diễn bằng số ~2^{n}~ - ~x~.

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

$$\begin{array}{|l|l|} \hline \mbox{Biễu diễn số bù }2 & \mbox{Giá trị} \\ \hline 000 & 0 \\ \hline 001 & 1 \\ \hline 010 & 2 \\ \hline 011 & 3 \\ \hline 100 & -4 \\ \hline 101 & -3 \\ \hline 110 & -2 \\ \hline 111 & -1 \\ \hline \end{array}$$

Ư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^{n} = 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 \geq 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^{n} -1-x~, do đó ~(NOT~ ~x) + 1 = 2^{n} -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.

Input

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 \leq n \leq 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.

Output

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.

Sample Input

3
110
011
4
0011
1110
0

Sample Output

overflow
1010

Comments

Please read the guidelines before commenting.


There are no comments at the moment.