1794: 寻找相似度

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：34 解决：16

题目描述

尤里和尤安是一对亲兄弟，在他们的家乡有一种非常有趣的游戏，两个人分别说出一个非负整数x，y，比较每个对应的位数i（i>=1），如果第i位上的值 a[i] b[i]相同且大于0则第i位的相似度为i，反之则为0，而两个数字x，y的相似度为各个位数相似度的和（比如：123和145，i=3时a[i]=b[i]，所以第3位相似度为3，其他位数相似度为0，总相似度为3）。但是尤里和尤安并不会十进制的计算，他们希望利用 转换后的二进制 进行计算，每个数字每个位数上的数值 可以两两自由交换，现在请问两人 最少 需要进行多少次交换才能得到 最大的相似度 。

输入

第一行输入一个正整数t，表示有t组测试样例，接下来t行每行两个正整数x，y。

输出

输出t行，每行两个整数sum1，sum2，分别表示交换总次数的最小值、最大相似度。

样例输入复制

2 8 9 2 9

样例输出复制

0 4 1 2

提示

x,y<=1e9,t<=1e5

样例：8，9的二进制表示分别为（1000）（1001）无需交换发现第四位相似度为4，其他位数（无法匹配）相似度为0

2，9的二进制表示分别为（10）（1001）9交换第2位和第4位（0011）（10）发现第二位相似度为2，其他位数（无法匹配）相似度为0

（注意：不存在的位数不可以交换）

Baidu
map