Hanojaus bokštai


Pradinių duomenų failas:
hanoj.in  
Rezultatų failas:
hanoj.out  
Laiko apribojimas:
1 s.  
Atminties apribojimas:
16 Mb.  

Užduotis

Hanojaus bokštų uždavinį 1883 metais suformulavo prancūzų matematikas Eduardas Lukas (Edouard Lucas). Duoti trys stiebai ir aštuoni skirtingo dydžio diskai. Iš pradžių visi šie diskai sumauti ant pirmojo stiebo: apačioje pats didžiausias diskas, ant jo – mažesnis ir t. t. Viršuje užmautas pats mažiausias iš diskų. Uždavinys prašo perkelti visus diskus nuo pirmojo stiebo ant paskutiniojo laikantis tokių taisyklių:

  • Vienu ėjimu galima kelti tik vieną diską.
  • Diską galima užmauti tik ant tuščio stiebo, arba uždėti ant didesnio už jį disko.

 

Mes praplėsime standartinę uždavinio formuluotę: vietoje aštuonių, reikia perkelti N diskų. Mūsų uždavinyje stiebai yra pavadinti raidėmis A, B ir C. Parašykite programą, kuri atspausdintų ėjimus, kuriuos reikia atlikti, kad diskus perkeltume nuo stiebo A ant stiebo C, laikantis minėtųjų taisyklių. Atliekamų ėjimų skaičius turi būti minimalus.

Pradiniai duomenys

Pradinių duomenų faile įrašytas vienintelis sveikas skaičius N (1 <= N <= 15) – diskų skaičius.

Rezultatai

Rezultatų failą turi sudaryti seka ėjimų, kuriuos atlikus, visi diskai būtų perkelti nuo stiebo A ant stiebo C. Ėjimas aprašomas formatu X -> Y (čia X ir Y yra stiebų vardai A, B arba C). Užrašas X -> Y reiškia, kad nuo stiebo X reikia paimti mažiausią (taigi viršuje esantį) diską ir užmauti ant stiebo Y.

Pavyzdžiai

Pradiniai duomenys Rezultatai
3
A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C