- Pradinių duomenų failas:
- hanoj.in
- Rezultatų failas:
- hanoj.out
- Laiko apribojimas:
- 1 s.
- Atminties apribojimas:
- 16 Mb.
Užduotis
Hanojaus bokštų žaidime poziciją galime aprašyti sveikųjų skaičių seka D = (\(d_{1}\), \(d_{2}\), …, \(d_{n}\)), \(d_{i}\) žymint, ant kurio stiebo šiuo metu užmautas i-asis diskas. Čia n yra diskų skaičius galvosūkyje. Diskai numeruojami nuo 1 iki n, pradedant nuo mažiausio.
Panagrinėkime, kaip atrodo žaidimo būsenos D su trimis diskais:
| Atlikta ėjimų | Diskai ant 1 stiebo | Diskai ant 2 stiebo | Diskai ant 3 stiebo | Žaidimo būsena D |
|---|---|---|---|---|
| 0 | 1, 2, 3 | – | – | (1, 1, 1) |
| 1 | 2, 3 | – | 1 | (3, 1, 1) |
| 2 | 3 | 2 | 1 | (3, 2, 1) |
| 3 | 3 | 1, 2 | – | (2, 2, 1) |
| 4 | – | 1, 2 | 3 | (2, 2, 3) |
| 5 | 1 | 2 | 3 | (1, 2, 3) |
| 6 | 1 | – | 2, 3 | (1, 3, 3) |
| 7 | – | – | 1, 2, 3 | (3, 3, 3) |
Parašykite programą, kuri pagal diskų skaičių n ir duotą žaidimo poziciją D nustatytų, ar ši pozicija pasiekiama optimaliai sprendžiant Hanojaus bokštų galvosūkį. O jei pasiekiama – išvestų, kiek ėjimų atliekama prieš pasiekiant šią žaidimo poziciją.
Pradiniai duomenys
Pirmoje pradinių duomenų eilutėje įrašytas diskų skaičius n (1 ≤ n ≤ 31). Kitose n eilučių įrašyti skaičiai \(d_{1}\), \(d_{2}\), …, \(d_{n}\) (1 ≤ \(d_{1}\), \(d_{2}\), …, \(d_{n}\) ≤ 3).
Rezultatai
Į rezultatus turi būti įrašomas vienintelis skaičius – ėjimų skaičius, arba -1, jei tokia žaidimo būsena nėra pasiekiama optimaliai žaidžiant.
Pastaba: akivaizdu, kad optimaliai žaidžiant ta pati būsena nebus sutikta du kartus, todėl atsakymas bus vienareikšmis.
Pavyzdys
| Pradiniai duomenys | Rezultatai |
|---|---|
3 2 2 1 |
3 |