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.
Celem w tej zabawie jest przeniesienie wieży z jednego słupka na drugi w najmniejszej, możliwej liczbie ruchów.
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