COCI '19 Contest 3 #5 Sob

View as PDF

Submit solution

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

Problem types

It was a dark and dreary Christmas Eve when our hero pondered, weak and weary, over a quaint and curious COCI task. When he nodded, nearly napping, suddenly he heard a tapping, tapping and a mighty roar. A giant reindeer broke through his chamber door, merely this and nothing more. While our hero's heart slightly fluttered, the beast simply uttered: "I won't leave until you solve this problem".

In the problem, you were given two integers N and M and you were supposed to perfectly match the numbers from sets A = \{0, 1, 2, \dots, N-1\} and B = \{M, \dots, M+N-1\} into N pairs, such that for the matched numbers x \in A and y \in B it holds x \mathbin{\&} y = x, where \& denotes a bitwise AND operation.


The first line contains two integers N and M (1 \le N \le M, N+M \le 10^6) from the task description.


You should output N lines and in each line you should output two integers x and y, where x belongs to set A and y belongs to set B. Numbers in each line should correspond to one of the matched pairs from the task description.

It is possible to prove that the solution always exists.


Subtask Score Constraints
1 10 N is a power of 2
2 29 N+M is a power of 2
3 39 N+M \le 1000
4 32 No additional constraints.

Sample Input 1

1 3

Sample Output 1

0 3

Sample Input 2

3 5

Sample Output 2

0 5
1 7
2 6

Sample Input 3

5 10

Sample Output 3

0 12
1 13
2 10
3 11
4 14


There are no comments at the moment.