Revenge of the Clocks (ripped off USACO)There are 9 clocks, arranged in a 3x3 array. They are labelled
A B C
D E F
G H I
Each clock is set to either one o'clock, two o'clock, three o'clock, ... or twelve o'clock.
There are nine possible moves, numbered from 1 to 9. Each move advances a certain set of clocks by 1 hour. The moves and their corresponding sets of clocks are:
1 ABDE 2 ABC 3 BCEF 4 ADG 5 BDEFH 6 CFI 7 DEGH 8 GHI 9 EFHI
We wish to know the shortest sequence of moves that will restore all the clocks to 12 o'clock.
For example, suppose A, B, and C are initially set to eleven o'clock, D, E, and F are set to twelve o'clock, and G, H, and I are set to ten o'clock. Then, doing move 2 once and move 8 twice resets all the clocks.
9 lines, containing one integer each, the initial states of clocks A, B, C, D, E, F, G, H, and I, respectively, where 1 denotes 1 o'clock, 2 denotes 2 o'clock, and so on.
9 lines, containing one integer each. Line #n should contain the number of times to do move #n in the shortest possible sequence of moves.
11 11 11 12 12 12 10 10 10
0 1 0 0 0 0 0 2 0
Point Value: 15
Time Limit: 2.00s
Memory Limit: 16M
Added: Dec 01, 2008
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3