hanoi4

Hanoi4

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

==Include(page="template/taskheader" task_id="hanoi4")==

Poveste ...
 
h2. Cerinta
 
...
 
h2. Restrictii
 
...

Cunoastem cu totii problema clasica a celor $3$ turnuri (stive) din Hanoi. Pe una din cele $3$ stive se afla $N$ discuri, in ordine crescatoare (de la varf catre baza) a dimensiunii. Se pot efectua mutari, o mutare constand in luarea unui disc din varful uneia din cele $3$ stive si plasarea lui in varful alteia, cu conditia ca, la nici un moment, pe nici o stiva, sa nu existe un disc de dimensiune mai mare peste un disc de dimensiune mai mica. Se stie ca numarul minim de mutari necesar pentru a muta cele $N$ discuri de pe stiva pe care se afla ele initial, pe o alta, avand la dispozitie doar $3$ stive, este $2^N^-1$. Dumneavoastra trebuie sa determinati numarul minim de mutari necesar pentru a muta $N$ discuri de pe o stiva pe alta, avand la dispozitie, in total, $4$ stive.

h2. Date de intrare

...

In fisierul de intrare $hanoi4.in$ se afla un singur numar intreg: $N$

h2. Date de iesire

...

In fisierul de iesire $hanoi4.out$ veti afisa o singura valoare intreaga: numarul minim de mutari cerut.

h2. Exemplu

h2. Restrictii si precizari:

| hanoi4.in | hanoi4.out |
| linia1
linia2
linia3
| linia1
linia2
|

* $1 ≤ N ≤ 1000$
* Rezultatul se incadreaza intr-un intreg pe $64$ de biti.

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

h2. Exemple:
 
table(example). |_. hanoi4.in |_. hanoi4.out |
| 7 | 25 |
| 64 | 18433 |
 
==Include(page="template/taskfooter" task_id="hanoi4")==
 
 

1316