W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
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:
Krążki nałożone na jeden słupek nazwiemy wieżą. Podsumowując powyższe zasady, możemy stwierdzić, że:
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 .
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 .
Program powinien czytać dane z wejścia standardowego. W pierwszym wierszu podana jest liczba (), oznaczająca liczbę krążków.
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.
Dla danych wejściowych:
6
poprawną odpowiedzią jest:
45