← 返回题目列表

Codeforces · 2187/B

B. 有史以来最短的声明

中文机器翻译题面 查看原题

给你两个非负整数 $$$x$$$, $$$y$$$。找到两个非负整数 $$$p$$$ 和 $$$q$$$,使得 $$$p\;\&\;q=0$$$ 且 $$$|x-p|+|y-q|$$$ 最小化。其中$$$\&$$$表示按位与运算。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的唯一行包含两个非负整数 $$$x$$$ 和 $$$y$$$ ($$$0 \le x,y \lt 2^{30}$$$)。

输出

对于每个测试用例,输出您找到的两个非负整数 $$$p$$$ 和 $$$q$$$。如果有多对 $$$p$$$ 和 $$$q$$$ 满足条件,则可以输出其中任何一个。

可以证明,在问题的约束下,任何有效解都满足$$$\max(p,q) \lt 2^{31}$$$。

示例

输入
复制

7
0 0
1 1
3 6
7 11
4 4
123 321
1073741823 1073741822

输出
复制

0 0
2 1
3 8
6 9
4 3
128 321
1073741824 1073741822

注意

在第一个测试用例中,一个有效的对是 $$$p=0$$$ 和 $$$q=0$$$,因为 $$$0\,\&\,0=0$$$ 和 $$$|x-p|+|y-q|=|0-0|+|0-0|=0$$$ 是 $$$p$$$ 和 $$$q$$$ 的所有对中的最小值。

在第三个测试用例中,一个有效的对将是 $$$p=3$$$ 和 $$$q=8$$$,因为 $$$3\,\&\,8=0$$$ 和 $$$|x-p|+|y-q|=|3-3|+|8-6|=2$$$ 是所有 $$$p$$$ 和 $$$q$$$ 对中的最小值。请注意,$$$(p,q)=(3,4)$$$ 也是有效的对。