Codeforces Beta Round #99 (Div. 1) B : Digits Permutations
問題概要
長さL(<10^5)の数字Nが与えられる。Nを適当に並び替えて(leading zeroもOK)ふたつの数A,Bをつくり、A+Bが10^kの倍数になるようにしたい。そのようなA,Bを出力する問題。
解法
1桁目は和が10になるようにして、それ以降は和が9になるのを選ぶ。そして0が余っていたらそれを末尾につける。
acceptされたコード
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAX_L = 1e5; char buf[MAX_L + 1], s1[MAX_L + 1], s2[MAX_L + 1], t1[MAX_L + 1], t2[MAX_L + 1]; int ds[10], ts[2][10]; void init(){ scanf("%[^\n]%*c", buf); } void prn(int key){ const int L = strlen(buf); for(int i=0; i<10; i++){ ts[0][i] = ds[i]; ts[1][i] = ds[i]; } int p = 0; ts[0][key]--; ts[1][(10-key)%10]--; s1[p] = key + '0'; s2[p++] = (10-key)%10 + '0'; for(int i=0; i<L; i++){ bool update = false; for(int i=0; i<10; i++){ if(ts[0][i] > 0 && ts[1][9-i] > 0){ ts[0][i]--; ts[1][9-i]--; s1[p] = i + '0'; s2[p++] = 9-i+'0'; update = true; break; } } if(!update){ break; } } int q = 0; for(; ts[0][0] > 0 && ts[1][0] > 0; ){ ts[0][0]--; ts[1][0]--; t1[L-1-q] = t2[L-1-q] = '0'; q++; } for(int i=0; i<p; i++){ t1[L-1-q] = s1[i]; t2[L-1-q++] = s2[i]; } while(q<L){ for(int i=9; i>=0; i--){ if(ts[0][i] > 0){ ts[0][i]--; t1[L-1-q] = i + '0'; break; } } for(int i=9; i>=0; i--){ if(ts[1][i] > 0){ ts[1][i]--; t2[L-1-q++] = i + '0'; break; } } } puts(t1); puts(t2); } int check(int x){ const int L = strlen(buf); for(int i=0; i<10; i++){ ts[0][i] = ds[i]; ts[1][i] = ds[i]; } int ans = 1; if(--ts[0][x] < 0){ return -1; } if(--ts[1][(10-x)%10] < 0){ return -1; } for(int i=0; i<L; i++){ bool update = false; for(int i=0; i<10; i++){ if(ts[0][i] > 0 && ts[1][9-i] > 0){ ts[0][i]--; ts[1][9-i]--; update = true; ans++; break; } } if(!update){ break; } } return ans + min(ts[0][0], ts[1][0]); } void solve(){ for(int i=0; buf[i]; i++){ ds[buf[i] - '0']++; } if(0)for(int i=0; i<10; i++){ printf("%d\n", ds[i]); } int best = -1, key = -1; for(int i=1; i<10; i++){ int score = check(i); if(best < score){ best = score; key = i; } } if(key > 0){ prn(key); } else{ const int L = strlen(buf); sort(buf, buf+L); reverse(buf, buf+L); puts(buf); puts(buf); } } int main(){ init(); solve(); return 0; }