2370. Crazy Bits

单点时限: 2.0 sec

内存限制: 256 MB

Olandicans have invented a strange computer; it has only 12-bit registers to store numbers. And the only command that this computer accepts is SWAP. The Swap function is called with 3 parameters i, j, and d. A call of swap(i, j, d) swaps the jth bit of the ith register with its neighboring bit in direction d (0: up, 1: right, 2: down, 3: left). For example, swap (2, 3, 1) swaps the 3rd and the 4th bits of the 2nd register and Swap(6, 4, 2) swaps the 4th bits of the 6th and the 7th registers. Olandicans know the initial values of the registers and they want to change them to some other numbers. They asked you to help them find the minimum number of swap calls.

输入格式

The input consists of multiple test cases. The first line of each test case is n (1 ≤ n ≤ 16), the number of registers. The next line contains n integers, where the ith number is the initial value of the ith register. The next line contains n integers, where the ith number is the desired value of the ith register. The input is terminated by a line containing a zero.

输出格式

For each test case, you should write a single line containing the minimum number of swaps needed for that test case. If it is not possible, write “Impossible”.

样例

Input
2
2 3
6 2
3
1 1 1
2 3 4
4
5 2 6 0
3 2 2 4
0
Output
3
Impossible
2

4 人解决,11 人已尝试。

5 份提交通过,共有 31 份提交。

8.6 EMB 奖励。

创建: 11 年,10 月前.

修改: 2 年,11 月前.

最后提交: 11 年,10 月前.

来源: Tehran 2007-2008

题目标签