COCI 2019/2020 - Contest 3 - Sob

View as PDF

Submit solution

Points: 1.00 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Suggester:
Problem source:
COCI 2019/2020 - Contest 3
Problem types
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Đó là một đêm Giáng sinh u ám và ảm đạm khi người hùng của chúng ta bế tắc trước một bài toán COCI kỳ lạ. Khi anh ta gần chợp mắt do kiệt sức, một tiếng gầm mạnh mẽ bỗng vang lên. Một con tuần lộc khổng lồ đã phá cửa nhà của anh ta và xông vào! Trong khi người hùng của chùng ta còn chưa kịp hoàng hồn, con thú chỉ đơn giản thốt lên: "Ta sẽ không rời khỏi đây cho đến khi người giải quyết bài toán này".

Trong bài toán, chúng ta được cho hai số nguyên ~N~ and ~M~ và phải tìm ra cách để nối các số giữa tập hợp ~A=\{0,1,2,...,N−1\}~ và ~B=\{M,...,M+N−1\}~ thành ~N~ cặp, sao cho với mọi cặp ~x~ và ~y~ (~x \in A~, ~y \in B~) thỏa mãn ~x\:\&\:y=x~, trong đó ~\&~ biểu thị toán tử thao tác bit ~AND~.

Input

Dòng đầu tiên chứa hai số nguyên ~N~ và ~M~ ~(1 \leq N \leq M, N+M \leq 10^{6})~ được nhắc đến ở đề bài.

Output

In ra ~N~ dòng, mỗi dòng chứa hai số nguyên ~x~ và ~y~ (~x \in A~, ~y \in B~) thỏa mãn một cặp nối được nhắc đến ở đề bài.

Có thế chứng minh được rằng luôn tồn tại một cách nối thỏa mãn đề bài.

Subtask

  • ~4~ test có ~N~ là lũy thừa của ~2~
  • ~7~ test khác có ~N+M~ là lũy thừa của ~2~
  • ~7~ test khác có ~N+M \leq 1000~
  • ~7~ test còn lại không có ràng buộc gì thêm.

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

Comments

Please read the guidelines before commenting.


There are no comments at the moment.