spoj1182Sorted bit squence[디지털 dp]

Description
Let's consider the 32 bit representation of all integers i from m up to n inclusive (m ≤ i ≤ n; m × n ≥ 0, -2^31 ≤ m ≤ n ≤ 2^31-1). Note that a negative number is represented in 32 bit Additional Code. That is the 32 bit sequence, the binary sum of which and the 32 bit representation of the corresponding positive number is 2^32 (1 0000 0000 0000 0000 0000 0000 0000 0000 in binary).
For example, the 32 bit representation of 6 is 0000 0000 0000 0000 0000 0000 0000 0110
and the 32 bit representation of -6 is 1111 1111 1111 1111 1111 1111 1111 1010
because
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)
Let's sort the 32 bit representations of these numbers in increasing order of the number of bit 1. If two 32 bit representations that have the same number of bit 1, they are sorted in lexicographical order.
For example, with m = 0 and n = 5, the result of the sorting will be
No.
Decimal number
Binary 32 bit representation
1
0
0000 0000 0000 0000 0000 0000 0000 0000
2
1
0000 0000 0000 0000 0000 0000 0000 0001
3
2
0000 0000 0000 0000 0000 0000 0000 0010
4
4
0000 0000 0000 0000 0000 0000 0000 0100
5
3
0000 0000 0000 0000 0000 0000 0000 0011
6
5
0000 0000 0000 0000 0000 0000 0000 0101
with m = -5 and n = -2, the result of the sorting will be
No.
Decimal number
Binary 32 bit representation
1
-4
1111 1111 1111 1111 1111 1111 1111 1100
2
-5
1111 1111 1111 1111 1111 1111 1111 1011
3
-3
1111 1111 1111 1111 1111 1111 1111 1101
4
-2
1111 1111 1111 1111 1111 1111 1111 1110
Given m, n and k (1 ≤ k ≤ min{n − m + 1, 2 147 473 547}), your task is to write a program to find a number corresponding to k-th representation in the sorted sequence.

Input

The input consists of several data sets. The first line of the input file contains the number of data sets which is a positive integer and is not bigger than 1000. The following lines describe the data sets.
For each data set, the only line contains 3 integers m, n and k separated by space.

Output

For each data set, write in one line the k-th number of the sorted numbers.

Example

Sample input:
2
0 5 3
-5 -2 2

Sample output:
2
-5 

여러가지 안되는 오류==초기화를 잊고 앞뒤가 맞지 않아 T^T가 하루종일 끊겼네
우리는 우선 m, n이 같은 상황을 고려한다.정렬의 첫 번째 키워드는 1의 수량이고 두 번째 키워드는 수의 크기이기 때문에 우리는 답안 중의 1의 개수를 쉽게 확정할 수 있다. 순서대로 구간 [m, n] 내의 2진법은 1의 수량이 0,1,2,... 이라는 것을 나타낸다. 누적된 답안이 k를 초과할 때까지 현재 값은 답안이 1을 포함하는 개수이고 가설은 s이다.예일의 알고리즘을 이용하면 이 문제를 해결할 수 있다.동시에 우리는 답이 몇 번째 [m, n]에 s개 1이 포함된 수를 구했다.따라서 2분의 답안으로 [m,ans]에 s개 1이 포함된 개수를 구해 판단하면 된다.매번 질문의 복잡도는 O(log(n))이기 때문에 2분의 복잡도는 O(log2(n))이다. 이것은 예처리의 복잡도이기도 하기 때문에 이 알고리즘은 비교적 이상적이다.m<0의 경우 처리하기 어렵지 않습니다. 우리는 모든 수의 최고위를 무시하고 답을 구한 후에 최고위를 1로 되돌려줍니다.

/**********************
spoj1182
2016.2.17
3379	0
C++ (g++ 4.9.2)
	1526
2016-02-17 14:42:14
**********************/
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,k,f[33][33];
void init()
{
    f[0][0]=1;
    for(int i=1;i<=32;i++)
    {
        f[i][0]=f[i-1][0];
        for(int j=1;j<=i;j++) f[i][j]=f[i-1][j-1]+f[i-1][j];
    }
}
int cal(int x,int k)
{
    int sum=0,tot=0,pos=0;
    int bit[33];
    memset(bit,0,sizeof(bit));
    while(x)
    {
        bit[++pos]=x%2;
        x/=2;
    }
    for(int i=pos;i>=1;i--)
    {
        if(!bit[i]) continue;
        sum+=f[i-1][k-tot];
        tot++;
        if(tot>=k) break;
    }
    if(tot==k) sum++;
    return sum;
}
int fnd(int l,int r,int k)
{
    int i,num;
    for(i=1;i<=31;i++)
    {
        num=cal(r,i)-cal(l-1,i);
        if(num>=k) break;
        else k-=num;
    }
    int tmp=l;
    while(l<=r)
    {
        int mid=l+(r-l)/2;
        num=cal(mid,i)-cal(tmp-1,i);
        if(num>=k) r=mid-1;
        else l=mid+1;
    }
    return l;
}
int main()
{
   // freopen("cin.txt","r",stdin);
    int t;
    init();
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&m,&n,&k);
        if(m<0)
        {
            m&=~(1<<31);
            if(n==0)
            {
                n--;
                k--;
            }
            n&=~(1<<31);
           // printf("m=%d n=%d
",m,n);
            printf("%d
",(1<<31)|fnd(m,n,k));
        }
        else
        {
            if(m==0) k--,m++;
            printf("%d
",fnd(m,n,k));
        }
    }
    return 0;
}