1993 East-Central Regionals of the ACM International Collegiate Programming Contest

The Battle of Waterloo
held at The University of Waterloo 5-6 November 1993



Problem G
Double Trouble

The secret service of Hudonia has always had a strong appetite for strange numbers. This appetite seemed strongest when Hudonia was in trouble. The numbers they were looking for had the following property. Whenever you would right-rotate the number (that is, take away the last digit and put it in front of the number), you would end up with double the original number. Numbers possessing this property were called double-trouble numbers. For example, X = 421052631578947368 is a double-trouble number, since 2X = 842105263157894736 which is a right rotation of X.

The number X is a double-trouble number in the number system with base 10. Any number system with base p >= 2, however, has many such double-trouble numbers. In the binary number system (base p = 2), for example, we have the double-trouble numbers 01 and 0101. Notice that the leading zeros are necessary here in order to obtain the proper number after right rotation.

The secret service seemed to like the smallest double-trouble numbers in a number system most. For example, in the binary number system the smallest double-trouble number is 01. In the decimal (p = 10) number system, the smallest double-trouble number is 052631578947368421. Being a patriotic Hudonian, you are asked to write a program that computes for a given base p of a number system the smallest double-trouble number in that system.

The input file consist of a sequence of numbers, one per line, ended by end-of-file. Each number is less than 200. The output file consists of, for each number p in the input file, the smallest double-trouble number (including any necessary leading zeros) in the number system with base p. The double-trouble numbers are given in the format analogous to the example below and in the same order as in the input file. No blank line should appear at the end of the output. Digits in a base-p number system are given in decimal representation, and each digit (including the last one) is followed by a single space.

Sample input:

2 10 35

Sample output:

For base 2 the double-trouble number is
0 1
For base 10 the double-trouble number is
0 5 2 6 3 1 5 7 8 9 4 7 3 6 8 4 2 1
For base 35 the double-trouble number is
11 23