Not an official ACM page
[Problem D
| 1996 North-Central Regional problem set
| My ACM problem archive
| my home page]
1996 ACM North Central Programming Contest
November 9, 1996
Problem C -- Run, Run, Runaround Numbers
An N-digit runaround number is characterized as follows:
- It is an integer with exactly N digits, each of which is
between 1 and 9, inclusively.
- The digits form a sequence with each digit telling where the next
digit in the sequence occurs. This is done by giving the number of
digits to the right of the digit where the next digit in the sequence
occurs. If necessary, counting wraps around from the rightmost digit
back to the leftmost.
- The leftmost digit in the number is the first digit in the
sequence, and the sequence must return to this digit after all digits
in the number have been used exactly once.
- No digit will appear more than once in the number. This rule
was accidentally left out of the problem description at the
competition.
For example, consider the number 81362. To verify that this is a
runaround number, we use the steps shown below:
- Start with the leftmost digit, 8
8 1 3 6 2
-
- Count 8 digits to the right, ending on 6 (note the wraparound).
8 1 3 6 2
- -
- Count 6 digits to the right, ending on 2.
8 1 3 6 2
- - -
- Count 2 digits to the right, ending on 1.
8 1 3 6 2
- - - -
- Count 1 digit to the right, ending on 3.
8 1 3 6 2
- - - - -
- Count 3 digits to the right, ending on 8, where we began.
8 1 3 6 2
= - - - -
In this problem you will be provided with one or more input lines,
each with a single integer R having between 2 and 7 digits
followed immediately by the end of line. For each such number,
determine the smallest runaround number that is equal to or greater
than R. There will always be such a number for each of the
input numbers. Display the resulting number in the format illustrated
below. The last line of the input will contain only the digit 0 in
column 1.
Sample Solution, Java
Try the Java solution:
Sample Input
12
123
1234
81111
82222
83333
911111
7654321
0
Sample Output
Case 1: 13
Case 2: 147
Case 3: 1263
Case 4: 81236
Case 5: 83491
Case 6: 83491
Case 7: 913425
Case 8: 8124956
This page maintained by
Ed Karrels.
Last updated September 20, 1999