Algorithm 版 (精华区)

发信人: Lerry (想不开·撞树), 信区: Algorithm
标  题: IOI'94 - Day 2 - Problem 1: The Clocks
发信站: 哈工大紫丁香 (2002年03月29日13:25:57 星期五), 站内信件

IOI'94 - Day 2 - Problem 1: 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 t
he dials to 12 o'clock with as few moves as possible. There are nine differe
nt allowed ways to turn the dials on the clocks. Each such way is called a m
ove. Select for each move a number 1 to 9. That number will turn the dials 9
0' (degrees) clockwise on those clocks which are affected according to figur
e 2 below.
Input Data
Read nine numbers from the INPUT.TXT file. These numbers give the start posi
tions of the dials. 0=12 o'clock, 1=3 o'clock, 2=6 o'clock, 3=9 o'clock. The
 example in figure 1 gives the following input data file:
3 3 0
2 2 2
2 1 2
Output Data
Write to the OUTPUT.TXT file a shortest sequence of moves (numbers), which r
eturns all the dials to 12 o'clock. In case there are many solutions, only o
ne is required. In our example the OUTPUT.TXT file could look as follows:
5849
----------------------------------------------------------------------------
----
Move   Affected clocks
 1         ABDE
 2         ABC
 3         BCEF
 4         ADG
 5         BDEFH
 6         CFI
 7         DEGH
 8         GHI
 9         EFHI    (Figure 2)
----------------------------------------------------------------------------
----
Example of Method
Each number represents a time accoring to following table:
0 = 12 o'clock
1 = 3 o'clock
2 = 6 o'clock
3 = 9 o'clock
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
　

--
不在乎天长地久，就怕你从来没有！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]