HDU 4726 Kia's Calculation
5646 ワード
Kia's Calculation
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 295 Accepted Submission(s): 80
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
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
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 295 Accepted Submission(s): 80
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
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
Source
2013 ACM/ICPC Asia Regional Online —— Warmup2
Recommend
zhuyuanchen520
题意： 有2个合法的整数。 长度为 10^6。 数字的每一位都能移动， 但移动后的整数一定要是合法的， 即无前导零。 使得 A + B 最大
思路： 因为固定搭配不变
例如 要得到5 ， （0， 5）（1，4）（2，3） （6， 9） （7，8） 互不干扰。
如果就统计
A中 0~9分别出现多少个，
B中 0~9分别出现多少个。
除了第一位外， 其他位都是要大就大。
第一位不能出现0， 即可。
#include
#include
#include
using namespace std;
const int V = 1000000 + 50;
int a[20], b[20], T, s = 1;
char ch[V], dh[V], ans[V];
int main() {
int i, j, k;
scanf("%d", &T);
while(T--) {
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
scanf("%s%s", &ch, &dh);
int len = strlen(ch);
if(len == 1) {
printf("Case #%d: %d
", s++, (ch[0] - '0' + dh[0] - '0') % 10);
continue;
}
for(i = 0; ch[i]; ++i)
a[ch[i] - '0']++;
for(i = 0; dh[i]; ++i)
b[dh[i] - '0']++;
for(i = 0; i < len; ++i) { //
int flag = 0;
for(j = 9; j >= 0 && !flag; --j) { //
for(k = 0; k <= 9; ++k) {
if(j - k >= 0) {
if(i == 0 && (k == 0 || j - k == 0))
;
else {
if(a[k] > 0 && b[j - k] > 0) {
ans[i] = j + '0';
a[k]--;
b[j - k]--;
flag = 1;
break;
}
}
}
if(i == 0 && (k == 0 || j + 10 - k == 0))
;
else {
if(a[k] > 0 && b[j + 10 - k] > 0) {
ans[i] = j + '0';
a[k]--;
b[j + 10 - k]--;
flag = 1;
break;
}
}
}
}
}
ans[i] = '\0';
if(ans[0] == '0')
printf("Case #%d: 0
", s++);
else
printf("Case #%d: %s
", s++, ans);
}
}