COCI '23 Contest 5 #2 Bitovi

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

What came first, the chicken or the egg? Is it better to live a hundred years as a millionaire or seven days in poverty? How to become a chess grandmaster? How to raise blinds? How to pass the final exams? How to train a dragon? These are interesting questions we can ponder only after the competition, but now we offer one less interesting computer science problem.

You are given two sets of numbers A and B of size N. In one move, you can select an arbitrary element from set A and change one arbitrary digit (bit) in its binary representation. The resulting number must not be an element of set A immediately before the change.

For example, the number 5 in binary is 0101_2. In one move, it can become 13 = 1101_2, 1 = 0001_2, 7 = 0111_2, or 4 = 0100_2 if we change its 4th, 3rd, 2nd, or 1st bit, respectively.

Determine a sequence of moves by which set A becomes equal to set B. Sets are equal if they have the same size and there is no element in set A that does not belong to set B.

Note: The number of moves does not have to be minimal, but it must satisfy the task constraints.

Input Specification

The first line contains the integer N (1 \le N \le 2^{15}), the size of the sets A and B.

The second line contains N distinct integers a_i (0 \le a_i < 2^{15}), the elements of the set A.

The third line contains N distinct integers b_i (0 \le b_i < 2^{15}), the elements of the set B.

Output Specification

In the first line, print the number of required moves.

In the remaining lines, print the numbers x and y (0 \le x, y < 2^{15}) — we change the number x from set A to the number y. The numbers x and y must differ by exactly one bit, and x \in A and y \notin A must hold at the moment we execute the move.

The number of moves you make must not exceed 2^{19}. It can be shown that a solution always exists within the given constraints.

Constraints

Subtask Points Constraints
1 10 a_i, b_i \le 2^{14}
2 15 N \le 7
3 30 N \le 27
4 15 No additional constraints.

Sample Input 1

3
0 1 2
1 2 3

Sample Output 1

2
1 3
0 1

Explanation for Sample 1

If we first make the move 0 1, and then 1 3, between these two moves, set A would have two identical elements, which the task does not allow. A possible solution is 2 3, 0 2.

Sample Input 2

3
4 8 31
0 4 8

Sample Output 2

5
31 30
30 28
28 24
24 16
16 0

Explanation for Sample 2

31 = 11111_2. By removing bits from least to most significant, we obtain the numbers 30, 28, 24, 16, and 0 in sequence. After all moves, set A becomes equal to set B.

Sample Input 3

5
0 1 2 4 5
7 6 5 3 2

Sample Output 3

9
1 3
3 7
0 1
1 0
2 6
0 2
7 3
5 7
4 5

Comments

There are no comments at the moment.