网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[SPOJ1182]二进制列排序
成绩 | 开启时间 | 2014年09月19日 星期五 10:08 | |
折扣 | 0.8 | 折扣时间 | 2014年09月26日 星期五 10:08 |
允许迟交 | 是 | 关闭时间 | 2014年09月26日 星期五 10:08 |
输入文件 | sortbit.in | 输出文件 | 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值有可能大于这个数。
【来源】
ACM ICPC 2006, Asia Regional Contest, site Hanoi