碎纸机
时间限制:1秒 内存限制:256M
【问题描述】
公司现在要发明一种新的碎纸机,要求新的碎纸机能够把纸条上的数字切成最接近而不超过目标值。比如,目标值的值是 50,而纸条上的数字是 12346,应该把数字切成四部分,分别是 1、2、34、6。因为这样所得到的和 43 = (1 + 2 + 34 + 6) 是所有可能中最接近而不超过 50 的。(比如 1, 23, 4 和 6 就不可以,因为它们的和不如 43 接近 50,而 12, 34, 6 也不可以,因为它们的和超过 50 了。
碎纸还有以下三个要求:
1、如果目标的值等于纸条上的值,则不能切。
2、如果没有办法把纸条上的数字切成小于目标的值,则输出"error"。如目标的值是1而纸条上的数字是123,则无论你如何切得到的和都比1大。
3、如果有超过一种以上的切法得到最佳值,则输出"rejected"。如目标的值为15,纸条上的数字是111,则有以下两种切法11、1或者1、11.
你的任务是编写程序对数字进行划分以达到最佳值。
【输入格式】
输入包含若干组数据,每组数据占一行,包含两个数据,第一个为目标值 \(m\),第二个位纸张上数字序列。输入以0 0结束。
【输出格式】
对于每组测试数据,如果如果所有的组和都要比 \(m\) 要大则输出"error";如果有多个分组方案都能得到一个最接近 \(m\),则输出"rejected;如果只有唯一方案,则输出分组方案中每组和最大方案:分组方案的和按顺序数组每组数字。
【输入输出样例】
Input
50 12346
376 144139
927438 927438
18 3312
9 3142
25 1299
111 33333
103 862150
6 1104
0 0
Output
43 1 2 34 6
283 144 139
927438 927438
18 3 3 12
error
21 1 2 9 9
rejected
103 86 2 15 0
rejected
【数据说明】
对于 \(100\%\) 的数据,\(1≤m≤10^9\),数字序列不超过20位。。
【来源】
Mr.he