hanoi

Hanoi

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

Poveste şi cerinţă...

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 altei 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

h2. Date de intrare

Fişierul de intrare $hanoi.in$ ...

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

În fişierul de ieşire $hanoi.out$ ...

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. Exemplu
table(example). |_. hanoi.in |_. hanoi.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|5 4
|13

|
h3. Explicaţie