Bitovi
레이팅 미적용의견: 0
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 01012. In one move, it can become \(13 = 11012\), \(1 = 00012\),
\(7 = 0111\){2}, or \(4 = 0100\) 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.
Subtask 1 (10 points): \(a\)\(i\), b\(i \le 2^{14}\)
Subtask 2 (15 points): \(N \le 7\)
Subtask 3 (30 points): \(N \le 2^{7}\)
Subtask 4 (15 points): No additional constraints.
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\) different integers \(a@@RISE_MATH_BLOCK_0@@i < 2^{15}\)), the elements of the set \(A\).
The third line contains \(N\) different integers \(b@@RISE_MATH_BLOCK_1@@i < 2^{15}\)), the elements of the set \(B\).
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\) ∈\(A\) and \(y\) /∈\(A\) must hold at
the moment we execute the move.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 10점 | \(a\)\(i\), b\(i \le 2^{14}\) |
2 | 15점 | \(N \le 7\) |
3 | 30점 | \(N \le 2^{7}\) |
4 | 15점 | No additional constraints. |
3
0 1 2
1 2 32
1 3
0 13
4 8 31
0 4 85
31 30
30 28
28 24
24 16
16 05
0 1 2 4 5
7 6 5 3 29
1 3
3 7
0 1
1 0
2 6
0 2
7 3
5 7
4 5Clarification of the first example:
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. Another possible solution is 2 3, 0 2.
Clarification of the second example:
31 = 111112. 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.
평가 및 의견
Bitovi
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Bitovi