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;
}