2015弱校連萌11大決戦の背水一戦D.Divideバイナリ思考問題

http://www.bnuoj.com/v3/contest_show.php？cid=6869啱problem/D
Alice and Bob has found a island of treasure in byteland！The y find N kinds of treasure on the island，and each kind of treasure has a certain number，and as in byteland，the value of each treasure will be a power of 2，such as 1，2，4，8…Now the only proble Horedstrever。and the value of each parts is the sum of all treasure s'in this part，they want to make the difference between the value of two parts as smas possible，can you help them？
Input
First line of the input is a single integer T（1<=T==20）、indicating there re re re re re e e e test cases.For each test case、the first line containtegerN（2<=N==10^5）、indicate the differentinininininininininininininininindededededededededededestinininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininin= 10^9)、indicate there are xi-th treasure，and the value of each one is 2^ai.
Output
For each case，you Shouuld output a single line，first output「Case(Cut)」，where t indicating the case numbern between 1 and T，then a string with only'0'followed，indicate the minefireent。
Sample Input
3 2 0 2 2 1 4 0 1 1 1 2 1 1 3 1 4 0 2 1 2 1 2 1 1 3 1 1
Sample Output
Case菗1:10 Case萼2:1 Case菵3:0

/**
2015                D. Divide        
    ：        2^a[i] ，  x[i] ，          ，            
    ：      ，          。          ，jin[i]   i          ，num[i]  
             i    ，           1，         j，  2^j,   ，         ，  
              。       1      ，         0，    2，        。
*/
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn=100010;
int n,a[maxn],jin[maxn];
LL num[maxn],x[maxn];
int main()
{
    int T,tt=0;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        int maxx=-1;
        memset(num,0,sizeof(num));
        for(int i=0;i<n;i++)scanf("%d%lld",&a[i],&x[i]),maxx=max(maxx,a[i]),num[a[i]]+=x[i];
//        printf(">>>before");
//        for(int i=0;i<=maxx;i++)printf("%lld",num[i]);
//        printf("
");
        memset(jin,0,sizeof(jin));
        for(int i=0;i<=maxx;i++)
        {
            if(num[i]/2)jin[i+1]=1;
            num[i+1]+=num[i]/2;
            num[i]%=2;
        }
//        printf(">>>");
//        for(int i=0;i<=maxx;i++)printf("%lld",num[i]);
//        printf("
");
        bool flag=0;
        for(int i=maxx;i>=0;i--)
        {
            if(num[i]&&jin[i]==0)
            {
                maxx=i;
                flag=1;
                break;
            }
        }
        printf("Case #%d: ",++tt);
        if(flag==0)
        {
            puts("0");
            continue;
        }
        int i;
        for(i=0;i<maxx;i++)
        {
            if(num[i]==1)
            {
                num[i]=1;
                for(int j=i+1;j<maxx;j++)num[j]^=1;
                break;
            }
        }
        num[maxx]=(i==maxx);
        for(int i=maxx;i>=0;i--)
        {
            if(num[i]==1)
            {
                for(int j=i;j>=0;j--)printf("%lld",num[j]);
                break;
            }
        }
        printf("
");
    }
    return 0;
}