[SPOJ1182]二进制列排序

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file sortbit.in Output file sortbit.out

【题目描述】

让我们考虑m到n(含m,n)的所有整数i的32位二进制表示(m<=i<=n,m*n>=0,-2^31<=m<=n<=2^31-1)。注意,负数由32位补码表示。也就是说,一个负数的二进制表示与其相反数的二进制表示之和恰好等于2^32(二进制的1 0000 0000 0000 0000 0000 0000 0000 0000)

例如,6的32位二进制表示是0000 0000 0000 0000 0000 0000 0000 0110

-6的32位二进制表示是1111 1111 1111 1111 1111 1111 1111 1010

因为


0000 0000 0000 0000 0000 0000 0000 0110 (6)

+

1111 1111 1111 1111 1111 1111 1111 1010 (-6)

-------------------------------------------------

= 1 0000 0000 0000 0000 0000 0000 0000 0000 (2^32)


让我们将这些整数的32位二进制表示排序。排序方法是:先按照二进制表示中1的个数从小到大排,1的个数相同的32位二进制数按字典序排。注意,它们的长度都是32位。

例如,当m=0,n=5时,排序的结果如下:


当m=-5,n=-2时,排序的结果如下:



给出m,n,k(1<=k<=n-m+1),你的任务是写一个程序找到排序后m~n的整数中第k小的数。

【输入格式】

输入包含多组数据。

输入文件的第一行是一个不超过1000的正整数,代表数据组数。

接下来是若干组数据。

每组数据有一行3个空格隔开的整数m,n,k。数据范围见题目描述。

【输出格式】

对每组数据,输出排序后第k小的数。

【样例输入】

2
0 5 3
-5 -2 2

【样例输出】

2
-5

【提示】

原题中k<=2147473547,但这里的k值有可能大于这个数。

【来源】

SPOJ 1128 Sorted bit squence

ACM ICPC 2006, Asia Regional Contest, site Hanoi