ZOJ Problem Set - 1694
You have just been put in charge of developing a new shredder for the Shredding Company. Although a "normal" shredder would just shred sheets of paper into little pieces so that the contents would become unreadable, this new shredder needs to have the following unusual basic characteristics.
For example, suppose that the target number is 50, and the sheet of paper has the number 12346. The shredder would cut the sheet into four pieces, where one piece has 1, another has 2, the third has 34, and the fourth has 6. This is because their sum 43 (= 1 + 2 + 34 + 6) is closest to the target number 50 of all possible combinations without going over 50. For example, a combination where the pieces are 1, 23, 4, and 6 is not valid, because the sum of this combination 34 (= 1 + 23 + 4 + 6) is less than the above combination's 43. The combination of 12, 34, and 6 is not valid either, because 52 (= 12 + 34 + 6) is greater than the target number of 50.
There are also three special rules:
In order to develop such a shredder, you have decided to first make a simple program that would simulate the above characteristics and rules. Given two numbers, where the first is the target number and the second is the number on the sheet of paper to be shredded, you need to figure out how the shedder should "cut up" the second number.
The input consists of several test cases, each on one line, as follows:
Each test case consists of the following two positive integers, which are separated by one space: (1) the first integer (ti above) is the target number; (2) the second integer (numi above) is the number that is on the paper to be shredded.
Neither integers may have a 0 as the first digit, e.g., 123 is allowed but
0123 is not. You may assume that bother integers are at most 6 digits in length.
A line consisting of two zeros signals the end of the input.
For each test case in the input, the corresponding output takes one of the following three types:
In the first type, partj and sum have the following meaning:
Each number should be separated by one space.
The message error is printed if it is not possible to make any combination, and rejected if there is more than one possible combination.
No extra characters including spaces are allowed at the beginning of each line, nor at the end of each line.
43 1 2 34 6
Source: Asia 2002, Kanazawa (Japan)