#CW33. 异或搬运(xorpath)

异或搬运(xorpath)

题目描述

小 W 正在整理两个计数器。计数器中的数分别为非负整数 xx 和 yy。一次搬运操作会把第一个计数器减少 11,并把第二个计数器增加 11;当第一个计数器为 00 时不能进行操作。操作不会改变两个数的和。

对于每组初始值,小 W 可以选择任意次操作,也可以一次都不做。请在所有可能的最终状态中,先使 x⊕yx \oplus y 最大,再在取得最大值的方案中使操作次数最少。这里的 ⊕\oplus 表示按位异或。

输入格式

第一行一个整数 tt,表示测试组数。

接下来 tt 行每行两个整数 x,yx,y,满足 0≤x,y<2290 \le x,y < 2^{29}。

输出格式

对每组数据输出一行两个整数:最大的异或值,以及达到该值所需的最少操作次数。

样例 1 输入

3
3 1
0 5
6 4

样例 1 输出

4 3
5 0
10 4

样例 1 解释

第一组中总和始终为 44。把 xx 全部搬到 yy,得到 (0,4)(0,4),异或值为 44,需要 33 次操作;任何两个非负整数的异或都不超过它们的和,所以这已经是最大值。第二组不能操作,答案为 0⊕5=50 \oplus 5 = 5。第三组总和为 1010,搬运 44 次得到 (2,8)(2,8),二进制位没有重叠,异或值达到 1010。

数据范围

所有数据满足 1≤t≤100001 \le t \le 10000,0≤x,y<2290 \le x,y < 2^{29}。

数据类别 分值 测试点 附加条件
A 20 1∼31\sim 3 x,y≤100x,y \le 100
B 4∼84\sim 8 x,y<220x,y < 2^{20}
C 10 9∼129\sim 12 x=0x=0 或 y=0y=0
D 13∼1613\sim 16 t≤100t \le 100
E 40 17∼2017\sim 20 无附加限制