Fişierul intrare/ieşire:	hanoig.in, hanoig.out	Sursă	Campion 2006-2007
Autor	Emanuela Cerchez	Adăugată de	Savin Tiberiu •devilkind
Timp execuţie pe test	0.05 sec	Limită de memorie	5120 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Hanoig

Sa consideram 3 tije (notate A, B, C). Pe tija A se afla n discuri de k dimensiuni distincte d₁> d₂>...> d_k.
Mai exact, exista m₁ discuri de diametru d₁, m₂ discuri de diametru d₂, ..., m_k discuri de diametru d_k .
Evident, m₁ + m₂ + ... + 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₁ discuri de diametru d₁, apoi urmeaza cele m₂ discuri de diametru d₂, ...).
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.

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.

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₁ m₂ ... m_k.

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₁ + m₂ + ... + m_k discuri de pe tija A pe tija B.

Restrictii

• 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.

Exemplu

Cum se trimit solutii?