/ Vijos / 题库 /

碎纸机

碎纸机

时间限制: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

信息

ID
2452
难度
9
分类
搜索 点击显示
标签
(无)
递交数
1
已通过
1
通过率
100%
被复制
1
上传者