CLOCKS - The Clocks

no tags 

|-------|    |-------|    |-------|    
| | | | | | |
|---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 3*3 array (figure 1). The goal is to return all the dials to 12 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 1 to 9. That number will turn the dials 90' (degrees) clockwise on those clocks which are affected according to figure 2 below.

Move   Affected clocks
 1         ABDE
 2         ABC
 3         BCEF
 4         ADG
 5         BDEFH
 6         CFI
 7         DEGH
 8         GHI
 9         EFHI   (Figure 2)

Input

Read nine numbers from standard input. These numbers give the start positions of the dials. Each number represents a time according to following table:

0 = 12 o'clock
1 = 3 o'clock
2 = 6 o'clock
3 = 9 o'clock

Output

Write to the standard output the shortest sequence of moves (numbers), which returns all the dials to 12 o'clock. In case there are many solutions, write the solution which is the least in lexicographic order.

Example

Input:
3 3 0
2 2 2
2 1 2

Output:
4 5 8 9

Although not the solution, a longer sequence of valid moves is illustrated below:

3 3 0         3 0 0         3 0 0          0 0 0         0 0 0
2 2 2   5->   3 3 3   8->   3 3 3   4 ->   0 3 3   9->   0 0 0
2 1 2         2 2 2         3 3 3          0 3 3         0 0 0

hide comments
ALi Ibrahim: 2015-08-08 10:55:52

First Accepted :)

shiva_hellgeek: 2013-05-30 13:51:46

I used the worst possible method to solve this problem. Solved the entire problem on paper. :p


Added by:bsrk
Date:2010-08-22
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 VB.NET
Resource:IOI 94 - Day 2