题意:给出数字 n 和一个字符串,要求切割字符串,然后把他们的和加起来,找到一个比目标值小 但 尽可能接近目标值的和。
如果有多于一个这样组合的和就输出rejected,如果无法组成比它小的数则输出error,否则输出那个值 并 输出解决方案
const int N=20+5;
int n,m,t;
int i,j,k;
char s[N];
int a[N]; //记录可能的答案
int ans[N],ans_num; //记录最后的答案
int flag,len,num,maxx;
void DFS(int sum,const int pos)
//sum 代表当前的和,pos 代表已经切割到的位置
{
if(sum>k) return ;
if(pos==len){
if(maxx<=sum && sum<=k){
if(sum==maxx) flag=2;
else{
maxx=sum; flag=1;
//debug(num);
ans_num=num;
for(int i=0;i<num;i++) ans[i]=a[i];
}
}
return ;
}
int tmp=0;
for(int i=pos;i<len;i++){
tmp=tmp*10+s[i]-'0';
a[num++]=tmp;
DFS(tmp+sum,i+1);
num--;
}
return ;
}
int main()
{
//IOS;
while(~sd(k)){
ss(s);
if(k==0 && s[0]=='0') break;
len=strlen(s);
maxx=0,flag=0,num=0;
DFS(0,0);
if(flag==0) puts("error");
else if(flag==2) puts("rejected");
else{
printf("%d",maxx);
for(int i=0;i<ans_num;i++){
printf(" %d",ans[i]);
}
puts("");
}
}
//PAUSE;
return 0;
}