1237-Shredding Company

問題概要

新しいシュレッダーを作ることになった．
普通のシュレッダーでも十分文字を見えなくすることは出来る．しかし，新しいシュレッダーは以下のような特徴を持つ必要がある．

・シュレッダーは入力として，"対象の数"と数字列の書かれた紙を受けとる
・シュレッダーは数字列の書かれた紙を一つ以上の数値が含まれるように切断する
・分断された紙に書かれた数の合計は出来るだけ"対象の数"に近い必要がある．ただし"対象の数"を越えてはいけない

例えば対象の数が50で，数字列が12346だとしたら1，2，34，6のように分断して総和を34にするのが最もよい．
(例があるけど中略)

さらに特別なルールがいくつかある
・対象の数と数字列が一致した場合は紙を切らなくても良い
・対象の数以下に和を出来ない場合はerrorと出力すること
・対象の数に最も近い数になるようなパターンが2つ以上ある場合はrejectedと出力せよ

あなたは優秀なプログラマーなので，このシュレッダーをシミュレートするプログラムを書くように命じられた．

入力は精々6文字の数字列である．

解法

入力サイズが非常に小さいのでDFSするだけ．

実装(C++)

#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <deque>
#include <complex>
#include <string>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <valarray>
#include <fstream>
using namespace std;

typedef long long int lli;
typedef unsigned int uint;
typedef unsigned char uchar;
typedef unsigned long long ull;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RREP(i,x) for(int i=(x);i>=0;i--)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)

#define dout(...) printf(__VA_ARGS__);fflush(stdout);

int target;
string value;
int n;
vector<int> now;
int ans=1000000;
map<int,int> cnt;
vector<int> tmp;
void dfs(int k){
	if(target<0)return;
	if(n==k){
		cnt[target]++;
		if(ans>target){
			ans=target;
			tmp=now;
		}
	}else{
		//if(value[k]=='0'){
		//	now.push_back(0);
		//	dfs(k+1);
		//	now.pop_back();
		//}else
		{
			REP(j,n-k){
				string t=value.substr(k,j+1);
				int v=atoi(t.c_str());

				now.push_back(v);
				target-=v;
				dfs(k+j+1);
				target+=v;
				now.pop_back();
			}
		}
	}
}
int main(){
	for(;cin>>target>>value;){
		if(target==0&&value=="0")break;
		ans=1000000;
		n=value.size();
		cnt.clear();
		dfs(0);
		if(ans>999999){
			cout<<"error"<<endl;
		}else if(cnt[ans]>1){
			cout<<"rejected"<<endl;
		}else{
			cout<<target-ans;
			REP(i,tmp.size()){
				cout<<" "<<tmp[i];
			}
			cout<<endl;
		}
	}
	return 0;
}