HDU 4726 Kia's Calculation

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 

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

#include<map>   
#include<set>  
#include<ctime>    
#include<cmath>   
#include<stack>
#include<queue>     
#include<string>    
#include<vector>    
#include<cstdio>        
#include<cstring>      
#include<iostream>    
#include<algorithm>        
#include<functional>    
using namespace std;
#define ms(x,y) memset(x,y,sizeof(x))        
#define rep(i,j,k) for(int i=j;i<=k;i++)        
#define per(i,j,k) for(int i=j;i>=k;i--)        
#define loop(i,j,k) for (int i=j;i!=-1;i=k[i])        
#define inone(x) scanf("%d",&x)        
#define intwo(x,y) scanf("%d%d",&x,&y)        
#define inthr(x,y,z) scanf("%d%d%d",&x,&y,&z)      
#define infou(x,y,z,p) scanf("%d%d%d%d",&x,&y,&z,&p)     
#define lson x<<1,l,mid    
#define rson x<<1|1,mid+1,r    
#define mp(i,j) make_pair(i,j)    
#define ff first    
#define ss second    
typedef long long LL;
typedef pair<int, int> pii;
const int low(int x) { return x&-x; }
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int N = 1e6 + 10;
const double eps = 1e-8;
int T, a[N], b[N], c[N], d[N], aa[N], bb[N], n, cas = 1;
char A[N], B[N];

void calc()
{
  rep(i, 0, 9) aa[i] = a[i], bb[i] = b[i], c[i] = 0;
  per(i, 9, 0)
  {
    rep(j, 0, 9) rep(k, 0, 9)
    {
      if ((j + k) % 10 != i) continue;
      int cost = min(aa[j], bb[k]);
      c[i] += cost;
      aa[j] -= cost;
      bb[k] -= cost;
    }
  }
  per(i, 9, 0)
  {
    if (c[i] > d[i])
    {
      rep(j, 0, 9) d[j] = c[j];
      break;
    }
    if (c[i] < d[i]) break;
  }
}

int main()
{
  for (inone(T); T--; cas++)
  {
    rep(i, 0, 9) a[i] = b[i] = d[i] = 0;
    scanf("%s%s", A, B); n = strlen(A);
    rep(i, 0, n - 1) a[A[i] - '0']++;
    rep(i, 0, n - 1) b[B[i] - '0']++;
    if (n == 1)
    {
      printf("Case #%d: %d\n", cas, (A[0] + B[0] - '0' * 2) % 10);
      continue;
    }
    printf("Case #%d: ", cas);
    int res = 0, flag = 0;
    rep(i, 1, 9) rep(j, 1, 9)
    {
      if (!a[i] || !b[j]) continue;
      res = max(res, (i + j) % 10);
    }
    rep(i, 1, 9) rep(j, 1, 9)
    {
      if (!a[i] || !b[j]) continue;
      if (res != (i + j) % 10) continue;
      a[i]--; b[j]--;
      calc();
      a[i]++; b[j]++;
    }
    per(i, 9, 1) if (i && d[i]) { flag = 1; break; }
    if (res || !res && !flag) printf("%d", res);
    if (res || !res && flag) per(i, 9, 0) rep(j, 1, d[i]) printf("%d", i);
    putchar(10);
  }
  return 0;
}