ZOJ Problem Set - 3803
Let x is a binary number with n digits (AnAn-1An-2...A2A1). And we can encode it as G(x) = x ⊕ ⌊x / 2⌋ or as C(x) = (2n - x) mod 2n, where "⊕" is bitwise XOR operation and "⌊x⌋" indicates the largest integer which is not greater than x.
For some reasons, Alice encodes her password P into G(P), and additionally, she encodes P into C(P). And she writes G(P) and C(P) in a paper. However, something terrible happened. A bug ate some parts of the paper, so some digits are unreadable now. Alice is so worried that she want you to determine the values of these digits using the readable digits.
There are multiple test cases. For every test case, it has 2 lines of same number of digits describe G(P) and C(P). In every line, it only contains '1', '0' and '?'. Unreadable digits are denoted with symbol '?'. The length of every line in the input is up to 105.
If it is impossible to restore G(P) and C(P), you should output "IMPOSSIBLE" (without quotes).
If G(P) is unique, you should output "UNIQUE" (without quotes) in the first line. Then output restored G(P) and C(P) in the same format.
If there are two or more possible G(P) that can be restored using the readable digits. You should output "AMBIGUOUS" (without quotes) and the number of possible G(P). The number may be very large, so the answer should modulo 109 + 7.
1110 0101 11?? 01?? 111? 100?
UNIQUE 1110 0101 AMBIGUOUS 3 IMPOSSIBLE
HintIn the second sample case, the three possible situations are:
1.G(1001) = 1101, C(1001) = 0111
2.G(1010) = 1111, C(1010) = 0110
3.G(1011) = 1110, C(1011) = 0101
Author: LIN, Xi
Source: ZOJ Monthly, August 2014