hanoig

Hanoig

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

Poveste si cerinta...

Sa consideram $3$ tije (notate $A$, $B$, $C$). Pe tija $A$ se afla $n$ discuri de $k$ dimensiuni distincte $d{~1~}$> $d{~2~}$>...> $d{~k~}$.
Mai exact, exista $m{~1~}$ discuri de diametru $d{~1~}$, $m{~2~}$ discuri de diametru $d{~2~}$, ..., $m{~k~}$ discuri de diametru $d{~k~}$ .
Evident, $m{~1~}$ + $m{~2~}$ + ... + $m{~k~}$= $n$.
Discurile sunt asezate initial pe tija $A$ in ordinea descrescatoare a dimensiunilor, privind de la baza spre varf (deci la baza sunt cele $m{~1~}$ discuri de diametru $d{~1~}$, apoi urmeaza cele $m{~2~}$ discuri de diametru $d{~2~}$, ...).
La o mutare se poate deplasa un singur disc de pe o tija pe alta, dar niciodata nu va fi plasat un disc de diamentru mai mare peste un disc cu diametru mai mic.
Scopul este de a muta toate discurile de pe tija $A$ pe tija $B$, respectand permanent ordinea descrescatoare a dimensiunilor.
Tija $C$ poate fi folosita ca tija de manevra.
 
h2. Cerinta
 
Scrieti un program care sa determine numarul minim de mutari care trebuie sa fie executate pentru a deplasa cele $n$ discuri de pe tija A pe tija B.

h2. Date de intrare

...

Fisierul de intrare $hanoig.in$ contine pe prima linie numarul natural $k$, cu semnificatia din enunt. Pe cea de a doua linie se afla $k$ numere naturale separate prin cate un spatiu $m{~1~}$ $m{~2~}$ ... $m{~k~}$.
 

h2. Date de iesire

...

Fisierul de iesire $hanoig.out$ va contine o singura linie pe care va fi scris numarul minim de mutari care trebuie sa fie executate pentru a deplasa cele $n$= $m{~1~}$ + $m{~2~}$ + ... + $m{~k~}$ discuri de pe tija $A$ pe tija $B$.

h2. Restrictii

* $... ≤ ... ≤ ...$

* $0$ < $k$ &le; $1000$
* $0$ < $m{~i~}$ &le; $1000$, pentru orice $i$= $1$, $2$, ..., $k$
* Discurile nu sunt numerotate, prin urmare discurile avand aceeasi dimensiune sunt considerate identice.

h2. Exemplu
table(example). |_. hanoig.in |_. hanoig.out |

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

|2
2 3
|8

|

h3. Explicatie
 
...

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