IOI'94 - Giorno 2 - Problema 1: Gli orologi
|-------| |-------| |-------|
| | | | | | |
|---O | |---O | | O |
| | | | | |
|-------| |-------| |-------|
A B C
|-------| |-------| |-------|
| | | | | |
| O | | O | | O |
| | | | | | | | |
|-------| |-------| |-------|
D E F
|-------| |-------| |-------|
| | | | | |
| O | | O---| | O |
| | | | | | | |
|-------| |-------| |-------| (Figura 1)
G H I
Ci sono nove orologi in una matrice 3x3 (figura 1). L'obiettivo è
fare in modo che tutti gli orologi segnino le 12 con il minor numero di
mosse possibili. Ci sono nove diversi modi di spostare le lancette degli
orologi: ognuno di essi viene chiamato mossa. Indichiamo le mosse con un
numero da 1 a 9: quella mossa corrisponderà alla rotazione di 90
gradi in senso orario di alcuni degli orologi, secondo lo schema specificato
sotto (figura 2).
Dati di input
Il file INPUT.TXT contiene nove numeri. Questi numeri danno le
posizioni iniziali delle lancette: 0=ore 12, 1=ore 3, 2=ore 6, 3=ore 9.
L'esempio in figura 1 corrisponde al seguente contenuto del file:
3 3 0
2 2 2
2 1 2
Dati di output
I risultati vanno scritti sul file OUTPUT.TXT come la più
breve sequenza di mosse (numeri), che riportano tutti gli orologi alle
12. Se ci sono più soluzioni, se ne deve comunque presentare una
sola. Nel nostro esempio il file OUTPUT.TXT potrebbe essere come segue:
5849
Mossa Orologi coinvolti
1 ABDE
2 ABC
3 BCEF
4 ADG
5 BDEFH
6 CFI
7 DEGH
8 GHI
9 EFHI (Figura 2)
Esempio di metodo
Ogni numero rappresenta un orario, secondo lo schema seguente:
0 = ore 12
1 = ore 3
2 = ore 6
3 = ore 9
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