== include(page="template/taskheader" task_id="hanoig") ==
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$ în 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~}$, ...).
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 4B$, respectand permanent ordinea descrescatoare a dimensiunilor.
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.
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 câte un spatiu $m{~1~}$ $m{~2~}$ ... $m{~k~}$.
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$.
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$ <= $1000$
* $0$ < $m{~i~}$ <= $1000$, pentru orice $i$=$1$, $2$, ..., $k$
* $0$ < $k$ ≤ $1000$
* $0$ < $m{~i~}$ ≤ $1000$, pentru orice $i$= $1$, $2$, ..., $k$
* Discurile nu sunt numerotate, prin urmare discurile avand aceeasi dimensiune sunt considerate identice.
h2. Exemplu
