joc
A new game was invented
for planet Algorithm high school students, in order to test their intellectual
abilities.
In this game a sequence of n
base 10 digits is given. The task of the game is for commas to be inserted in
between some of these digits, so as to get a sequence of positive integers that
verifies the following properties:
the sequence is strictly ascending
and the last number in the sequence must have the smallest possible value.
E.g.: digit sequence 3546 can
be transformed in a sequence of numbers in the following way: by inserting commas
between 3 and 5
and between 5 and 4,
thus becoming 3,5,46. In case
there is more than one such sequence that verifies the above properties display
the one that has the highest value before the first comma; if there is still
more than one with this property display the one that has the highest value
between the first and second comma, and so on. Going back to the example above
we notice that for digit sequence 3546
there were two valid possible transformations: 3,5,46
or 35,46. The correct answer
for the game was: 35,46. It is
allowable that a number begin with a sequence of 0s.
Task
On Earth the game was implemented as part of the educational IT program and the task turned into: write a program which, when receiving as input a sequence of digits, obtains a sequence of numbers separated by commas that verify the above properties.
Input Data
Input file joc.in contains one or more sequences of no more than 200 digits, written one after the other, without any spaces in between them, each sequence being on a single line. The file ends in a sequence of only one digit: 0.
Output Data
Output file joc.out will contain a line for each sequence in the input file, on which it will be displayed the sequence of numbers obtained by inserting commas that verify the above properties, without any spaces between commas and numbers.
Constraints
Example
|
joc.in |
joc.out |
|
3467 |
3,4,6,7 |
Time limit: 0.25 seconds/test
prep. Florin Manea
University of Bucharest, Mathematics and IT Department
Contact: flmanea@gmail.com