Kia's Calculation

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 4054    Accepted Submission(s): 825

Problem Description

Doctor Ghee is teaching Kia how to calculate the sum of two integers. But Kia is so careless and alway forget to carry a number when the sum of two digits exceeds 9. For example, when she calculates 4567+5789, she will get 9246, and for 1234+9876, she will get 0. Ghee is angry about this, and makes a hard problem for her to solve: Now Kia has two integers A and B, she can shuffle the digits in each number as she like, but leading zeros are not allowed. That is to say, for A = 11024, she can rearrange the number as 10124, or 41102, or many other, but 02411 is not allowed. After she shuffles A and B, she will add them together, in her own way. And what will be the maximum possible sum of A "+" B ?

 

 

Input

The rst line has a number T (T <= 25) , indicating the number of test cases. For each test case there are two lines. First line has the number A, and the second line has the number B. Both A and B will have same number of digits, which is no larger than 10

⁶, and without leading zeros.

 

 

Output

For test case X, output "Case #X: " first, then output the maximum possible sum without leading zeros.

 

 

Sample Input

1

5958 3036

 

 

Sample Output

Case #1: 8984

 

 

Source

 

 

#include
      
       #include
       
        #include
        
         #include
         
          #define ls (u<<1)#define rs (u<<1|1)#define maxn 1000005#define ll long longusing namespace std;#define max(a,b)    (a)>(b)?(a):(b)#define min(a,b)    (a)<(b)?(a):(b)int a[10],b[10];char s1[maxn],s2[maxn],res[maxn];int main(){    int T;    scanf("%d",&T);    int t = 0;    while(T--){        for(int i=0;i<10;i++){            a[i]=0,b[i]=0;        }        scanf("%s%s",s1,s2);        int len = strlen(s1);        for(int i=0;i
          
           tmp){                            tmp = (i+j)%10;                            m=i,n=j;                        }                    }                }            }        }        res[0] = '0' + tmp; //第一位找到          if(res[0] == '0'){
    //如果第一位是0，说明后面也只能是0，直接输出0就可以了              printf("Case #%d: 0\n",++t);            continue;        }        a[m]--,b[n]--; //两个串相应的数字个数减少一个          int p = 1;        while(1){            int m,n,cnt=0;            tmp = -1;            for(int i=0;i<10;i++){                if(!a[i]){                    cnt++;                }            }            if(cnt == 10){                break;            }            for(int i=0;i<10;i++){                if(a[i]){                    for(int j=9;j>=0;j--){                        if(b[j]){                            int tmpt = (i+j)%10;                            if(tmpt>tmp){                                tmp = tmpt;                                m=i,n=j;                            }                        }                    }                }            }            int tm = min(a[m],b[n]);            //假设a，b组成一个值a，b这两个数都有多个，则直接减完，这样可以节省时间             a[m] -= tm,b[n] -= tm;//每次找到之后直接让一个个数或者两个个数都变为0             for(int k=p;k