IOI '94 - Haninge, Sweden

The Clocks

+-------+    +-------+    +-------+    
|       |    |       |    |   |   |    
|---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.

Example

The following is one possible series of moves that transforms all the clock from Figure 1 to 12:00. 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 Format

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

Output Format

A single line that contains a space separated list of the shortest sequence of moves (designated by numbers) which returns all the clocks to 12:00. 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

All Submissions
Best Solutions

Point Value: 10
Time Limit: 2.00s
Memory Limit: 8M
Added: Dec 26, 2013

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Hi I was getting a lot of RE so I looked up the error and it turned out to be that I have a queue that was too large I have put an if condetion that if my queue was bigger than a fixed number the program would stop adding now I'm getting AC on almost all the the tests there are tests 2 , 3 and 4 that give me WA and my program doesn't output anything and that's because of the queue limit can anyone help me to figure out what's wrong can someone put a like for a C++ soultion or look and my code and tell me where I'm wrong please I've coded and debugged more than 150 lines of code please help
link for my code: 
http://pastebin.com/srUbRkAZ