IOI '94 P4 - The Clocks

View as PDF

Points: 10
Time limit: 1.0s
Memory limit: 8M

Problem type
IOI '94 - Haninge, Sweden
+-------+    +-------+    +-------+
|       |    |       |    |   |   |
|---O   |    |---O   |    |   O   |
|       |    |       |    |       |
+-------+    +-------+    +-------+
A            B            C

+-------+    +-------+    +-------+
|       |    |       |    |       |
|   O   |    |   O   |    |   O   |
|   |   |    |   |   |    |   |   |
+-------+    +-------+    +-------+
D            E            F

+-------+    +-------+    +-------+
|       |    |       |    |       |
|   O   |    |   O---|    |   O   |
|   |   |    |       |    |   |   |
+-------+    +-------+    +-------+  (Figure 1)
G            H            I

There are nine clocks in a array (figure 1). The goal is to return all the dials to o'clock with as few moves as possible. There are nine different allowed ways to turn the dials on the clocks. Each such way is called a move. Select for each move a number to . That number will turn the dials degrees clockwise on those clocks which are affected.

Move Affected Clocks
1 ABDE
2 ABC
3 BCEF
5 BDEFH
6 CFI
7 DEGH
8 GHI
9 EFHI

Example

The following is one possible series of moves that transforms all the clock from Figure 1 to . However, note this is not the "correct" answer (see below).

9  9 12           9 12 12           9 12 12            12 12 12           12 12 12
6  6  6    5->    9  9  9    8->    9  9  9    4->     12  9  9    9->    12 12 12
6  3  6           6  6  6           9  9  9            12  9  9           12 12 12

Input Specification

The input contains three lines of three space-separated numbers; each number represents the start time of one clock, , , , or . The ordering of the numbers corresponds to the first example above.

Output Specification

A single line that contains a space separated list of the shortest sequence of moves (designated by numbers) which returns all the clocks to . If there is more than one solution, print the one which gives the lowest number when the moves are concatenated (e.g., 5 2 4 6 < 9 3 1 1).

Sample Input

9 9 12
6 6 6
6 3 6

Sample Output

4 5 8 9