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

Problema turnurilor din Hanoi este bine cunoscută: sunt $3$ tije şi $N$ discuri, oricare două discuri având raza diferită. Iniţial, cele $N$ discuri sunt aşezate pe prima tijă, discurile fiind ordonate de jos în sus descrescător în funcţie de rază. Astfel, discul cu raza cea mai mare este cel mai de jos iar discul cu raza cea mai mică cel mai de sus. Se doreşte mutarea discurilor de pe prima pe ultima tijă, efectuând un număr minim de mutări. O mutare constă în alegerea unei tije care conţine cel puţin un disc şi mutarea discului din vârf în vârful oricărei alte tije. Singura regulă este că un disc nu poate fi aşezat peste alt disc de rază mai mică.

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.

Există o legendă conform căreia într-o mănăstire din Tibet călugării au aşezat $N$ discuri pe prima tijă iar apoi au început să efectueze mutări astfel încât să le mute pe ultima tijă. Legenda spune că atunci când vor termina va avea loc sfârşitul lumii. Recent s-a descoperit că de fapt călugării foloseau $M$ tije în loc de $3$ şi că sfârşitul lumii s-ar putea să fie de fapt mult mai aproape.

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.

Să se determine numărul minim de paşi pentru a muta cele $N$ discuri de pe prima pe ultima tijă, ştiind că în total sunt $M$ tije care pot fi folosite.

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

Fişierul de intrare $hanoi.in$ conţine pe prima linie, separate de exact un spatiu, numerele $N$ si $M$, cu semnificaţia din enunţ.

Fişierul de intrare $hanoi.in$ contine pe prima linie, separate de exact un spatiu, numerele $N$ si $M$, cu semnificatia din enunt.

h2. Date de ieşire

Fişierul de ieşire $hanoi.out$ conţine o singură linie pe care se află răspunsul problemei.

Fişierul de ieşire $hanoi.out$ contine o singura linie pe care se afla raspunsul problemei.

h2. Restricţii
* $3 ≤ N ≤ 250$
* $3 ≤ M ≤ 150$

h2. Exemple

h2. Exemplu

table(example). |_. hanoi.in |_. hanoi.out |

|5 4|13|

|5 4
|13
|

h3. Explicaţie

Mai jos este prezentată o secvenţă posibilă cu numar minim de mutări pentru a aduce discurile de pe tija iniţială pe cea finală:
 
!problema/hanoi?hanoi.png!
 
În total au fost efectuate $13$ mutări.

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") ==

4823