Laiko ribojimas: 1s

Atminties ribojimas: 16MB

Duomenų failas: hanoj3.in

Rezultatų failas: hanoj3.out

Jei norite pateikti savo sprendimą - prisijunkite.

Hanojaus bokštai 3

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\\len\\le31). Kitose n eilučių įrašyti skaičiai d_1,d_2,...,d_n (1\\led_1,d_2,...,d_n\\le3).

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