题目描述
小蓝公司现在要发明一种新的碎纸机,要求新的碎纸机能够把纸条上的数字切成最接近而不超过target值。比如,target的值是50,而纸条上的数字是12346,应该把数字切成四部分,分别是1、2、34、6。因为这样所得到的和43 (= 1 + 2 + 34 + 6) 是所有可能中最接近而不超过50的。(比如1, 23, 4, 和6 就不可以,因为它们的和不如43接近50,而12, 34, 6也不可以,因为它们的和超过50了。碎纸还有以下三个要求:
1、如果target的值等于纸条上的值,则不能切。
2、如果没有办法把纸条上的数字切成小于target,则输出error。如target是1而纸条上的数字是123,则无论你如何切得到的和都比1大。
3、如果有超过一种以上的切法得到最佳值,则输出rejected。如target为15,纸条上的数字是111,则有以下两种切法11、1或者1、11.
你的任务是编写程序对数字进行划分以达到最佳值。
输入描述
输入由多个测试用例组成(最多100组),每个测试用例在一行上,每个测试用例由两个正整数组成,它们用一个空格分隔,第一个整数是目标数,第二个整数是要撕碎的纸张上的数字。,两个整数的长度最多为6位。
整数都不能将0作为第一个数字,例如,允许123,但不允许0123。
由两个零组成的行表示输入的结束。
输出描述
输入中的每个测试的情况下,相应的输出采取以下三种类型之一:
sum part1 part2 ...
rejected
error
在第一类型中,parti和sum具有以下含义:
1.每个parti都是被碎后的纸片的数字,parti的顺序对应于纸张上原始数字的顺序。
2.sum是被粉碎后的数字之和,即sum = part1 + part2 + ...
每两个数字应该用一个空格分隔。
如果无法进行任何组合,则会输出error ,如果存在多个可能的组合,则输出 rejected。 在每行的开头不允许包含空格等额外字符。
样例输入
50 12346
376 144139
927438 927438
18 3312
9 3142
25 1299
111 33333
103 862150
6 1104
0 0
样例输出
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
提示