magnify

Hanojaus bokštai 3

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
© Bronė Narkevičienė