2015
09-17

# Kia’s Calculation

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

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
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 106, 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

#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
int p[2][10];
char str1[1000050],str2[1000050];
int main ()
{
int tcase,a,b,num1,num2,i,j,k,tt=1;
scanf("%d",&tcase);
gets(str1);
while(tcase--)
{
gets(str1);
gets(str2);
num1=0;
memset(p,0,sizeof(p));
for(num1=0;str1[num1]!='\0';num1++)
{
p[0][str1[num1]-'0']++;
p[1][str2[num1]-'0']++;
}
printf("Case #%d: ",tt++);
bool flag=true,flag2=true;
int li;
for(i=0,li=9;i<num1;i++)
{

flag=true;
for(;li>=0&&flag;li--)
{
for(j=0;j<=9&&flag;j++)
{
k=(li-j+10)%10;
if(!i&&(!j||!k))
{
continue;
}
if(p[0][j]&&p[1][k])
{

p[0][j]--;p[1][k]--;
flag=false;
if(flag2&&li!=0)
printf("%d",li),flag2=false;
else if(!flag2)
printf("%d",li);
goto my;
}
}
}
my:;
if(!i)
li=9;
}
if(flag2)
{
printf("0\n");
}
else
printf("\n");

}
return 0;
}