It is known that Petka is fond of arithmetic. Many times he thought of
a positive integer and gave Chapaev the sum of its digits and the sum of
its squared digits, and Chapaev could always find the smallest number with
these properties very quickly. But Chapaev's answer never was the number
Petka had in mind. What could be done about that? What number should
Petka think of so that Chapaev would find just it?
Petka asked Furmanov to teach him how to determine whether a number was the smallest
one with the given sums of digits and squared digits. Furmanov was interested in
the problem. After some thought, he understood that the sums didn't depend on
the order of digits. Therefore, the digits in a “smallest” number
were always in ascending order, and there could be no zeros in such numbers.
Taking the problem seriously, he found out the following property: if some
digits were deleted from a “smallest” number, one that was left was
also a “smallest” number.
Then Furmanov understood that he could write several patterns that would
specify all the numbers Petka was interested in. It was sufficient to use
such patterns in which there would be asterisks in addition to digits, each
asterisk meaning that the preceding digit could appear in this place
an arbitrary number of times (including the case when it would be absent).
Furmanov took yesterday's copy of the Pravda and wrote a list of patterns on
the margins. His list was such that for any “smallest” number there
was a pattern matching it and any number matching any pattern was “smallest”.
Moreover, the list was the shortest possible. Can you repeat
Furmanov's heroic deed?
You are given the base of the number system for which it is required to make
the list (the base is in the range from 2 to 36).
Output the list of patterns sorted in the usual ascending order.
Each pattern may contain only digits of the given number system
(1, 2, …, 9, A, B, …) and an asterisk.
The patterns should not
contain unnecessary elements: instead of the pattern “12*2*3”
you should output “12*3”.
It is allowed that the empty string matches several patterns.
The numbers 222 and 1113 have the same sum of digits and the sum of squared
digits. That is why any number containing three ones and one three can be
“lessened” with the sums of digits and of squared digits preserved.
Problem Author: Vladimir Yakovlev
Problem Source: The 13th Urals Collegiate Programing Championship, April 04, 2009