Kia's Calculation

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 3902    Accepted Submission(s): 784

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

 

 

Recommend

zhuyuanchen520

/** @Author: lyuc* @Date:   2017-04-28 19:34:17* @Last Modified by:   lyuc* @Last Modified time: 2017-04-28 20:19:20*//*题意：定义一种加法法则，两个整数相加的时候不用进位，现在给你两个位数相等的整数，用着每个整数任意组合，让你构造出 *    两个数的和最大。 * *思路：先统计每个数中的0-9个出现了多少次，然后最高位特殊处理，剩下的都构造最大的数 */#include 
      
       #define MAXN 1000005using namespace std;int t;char s1[MAXN],s2[MAXN];int num[MAXN];//用来存放数字int vis[2][10];void init(){    memset(vis,0,sizeof vis);    memset(num,'\0',sizeof num);}int main(){    // freopen("in.txt","r",stdin);    scanf("%d",&t);    for(int ca=1;ca<=t;ca++){        printf("Case #%d: ",ca);        init();        scanf("%s%s",s1,s2);        int n=strlen(s1);        if(n==1){
    //如果只有一位的话，直接输出就可以了            printf("%d\n",(s1[0]-'0'+s2[0]-'0')%10);            continue;        }        //统计每个数字出现的次数        for(int i=0;i
       
        =0;i--){
    //i枚举的是给最后的和的第res位的数，因为要尽量找大的嘛，所以从9开始枚举                bool flag=false;                for(int j=0;j<=9;j++){                    if(vis[0][j]==0) continue;//如果第一个数中没有出现的数字那么根本不需要考虑了                    int ok=(i+10-j)%10;//ok表示和j(第一个数中出现的数字)组成i的在第二个数中出现的数字                    if(res==0&&(j==0||ok==0)) continue;//如果是res==0(当前枚举的是最高位，那么就不能出现前导零)                    if(vis[1][ok]){
    //如果ok在第二个数中还有那么就可以构造了                        vis[0][j]--;                        vis[1][ok]--;                        num[res]=i;                        flag=true;                        break;                    }                }                if(flag==true) break;            }        }        int res=0;        while(res