== include(page="template/taskheader" task_id="hanoi") ==

!> problema/hanoi?hanoi.png!

Problema turnurilor din Hanoi este bine cunoscuta: sunt $3$ tije si $N$ discuri, oricare doua discuri avand raza diferita. Initial, cele $N$ discuri sunt asezate pe prima tija, discurile fiind ordonate de jos in sus descrescator in functie de raza. Astfel, discul cu raza cea mai mare este cel mai de jos iar discul cu raza cea mai mica cel mai de sus. Se doreste mutarea discurilor de pe prima pe ultima tija cu numar minim de mutari. O mutare consta din alegerea unei tije care contine cel putin un disc si mutarea discului din varf in varful oricarei alte tije. Singura regula este ca un disc nu poate fi asezat peste alt disc de raza mai mica.

Exista o legenda conform careia intr-o manastire din Tibet calugarii au asezat N discuri pe prima tija iar apoi au inceput sa efectueze mutari astfel incat sa le mute pe ultima tija. Legenda spune ca atunci cand vor termina va avea loc sfarsitul lumii. Cum lucrurile sunt intotdeauna mai rele decat par, s-a descoperit ca de fapt calugarii foloseau $M$ tije in loc de $3$.

Exista o legenda conform careia intr-o manastire din Tibet calugarii au asezat $N$ discuri pe prima tija iar apoi au inceput sa efectueze mutari astfel incat sa le mute pe ultima tija. Legenda spune ca atunci cand vor termina va avea loc sfarsitul lumii. Recent s-a descoperit ca de fapt calugarii foloseau $M$ tije in loc de $3$ si ca sfarsitul lumii s-ar putea sa fie de fapt mult mai aproape.

Sa se determine numarul minim de pasi pentru a muta cele $N$ discuri de pe prima pe ultima tija, stiind ca in total sunt $M$ tije.

Sa se determine numarul minim de pasi pentru a muta cele $N$ discuri de pe prima pe ultima tija, stiind ca in total sunt $M$ tije care pot fi folosite.

h2. Date de intrare

h3. Explicaţie

...

move 1 from 1 to 3
move 2 from 1 to 2
move 1 from 3 to 2 atop 2
move 3 from 1 to 4
move 4 from 1 to 3
move 3 from 4 to 3 atop 4
move 5 from 1 to 4
move 3 from 3 to 1
move 4 from 3 to 4 atop 5
move 3 from 1 to 4 atop 4
move 1 from 2 to 1
move 2 from 2 to 4 atop 3
move 1 from 1 to 4 atop 2

== include(page="template/taskfooter" task_id="hanoi") ==