Dwubarwne wieże Hanoi

Limit pamięci: 32 MB

Wieże Hanoi to tradycyjna zabawa-łamigłówka polegająca na nakładaniu krążków na słupki. Dysponujemy krążkami o średnicach i trzema słupkami, które nazwiemy , i . Każdy krążek ma w środku dziurkę, która pozwala nałożyć krążek na słupek. Początkowo wszystkie krążki znajdują się na słupku i są ułożone począwszy od największego (na dole) do najmniejszego (na górze). Zabawa polega na przeniesieniu wszystkich krążków na jeden z wolnych słupków (powiedzmy ) zgodnie z następującymi zasadami:

• w jednym ruchu wolno nam wziąć jeden krążek leżący na górze na jednym ze słupków i położyć go na górze na innym słupku;
• na każdym słupku zawsze musi być zachowany porządek, tzn. krążki muszą leżeć w kolejności od największego (na dole słupka) do najmniejszego (na górze).

Krążki nałożone na jeden słupek nazwiemy wieżą. Podsumowując powyższe zasady, możemy stwierdzić, że:

• nie jest możliwe wyciągnięcie krążka ze środka wieży lub włożenie krążka do środka wieży;
• nie wolno brać więcej niż jeden krążek na raz;
• nie wolno kłaść większego krążka na mniejszym.

Dwubarwne wieże Hanoi, to nieco zmodyfikowana odmiana powyższej układanki. Jak poprzednio mamy trzy słupki i krążków o średnicach . Tym razem jednak krążki o średnicach nieparzystych () są białe, a krążki o średnicach parzystych () są czarne. Celem zabawy jest przeniesienie (zgodnie z podanymi wyżej zasadami) wszystkich krążków białych na słupek , a krążków czarnych na słupek .

Zadanie

Napisz program, który wyliczy minimalną liczbę ruchów, potrzebnych do ułożenia krążków białych na słupku , a krążków czarnych na słupku .

Wejście

Program powinien czytać dane z wejścia standardowego. W pierwszym wierszu podana jest liczba (), oznaczająca liczbę krążków.

Wyjście

Program powinien pisać wynik na wyjście standardowe. Wynikiem powinna być jedna liczba oznaczająca minimalną liczbę ruchów potrzebnych do rozdzielenia białych i czarnych krążków.

Przykład

Dla danych wejściowych:

6

poprawną odpowiedzią jest:

45