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 în ordinea descrescatoare a dimensiunilor, privind de la baza spre vârf (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, respectând 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 câte 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 si precizari

• 0 < k <= 1000
• 0 < m_i <= 1000, pentru orice i=1, 2, ..., k
• Discurile nu sunt numerotate, prin urmare discurile având aceeasi dimensiune sunt considerate identice.
  

Timp maxim de executie/test: 0.1 secunde

prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi
Contact:emanuela.cerchez@gmail.com