Dwójkowy zbijak [A]
Limit pamięci: 128 MB
Bituś i Bajtuś grają w "dwójkowego zbijaka". Gra toczy się na planszy złożonej
z pól ponumerowanych liczbami od 1 do . Na każdym polu stoi jeden pionek.
Gracze wykonują ruchy naprzemiennie. Ruch polega na zabraniu pionka z pola o numerze
i przesunięciu go na pole o numerze , dla dowolnego , o ile takie pole istnieje.
Jeśli na nowym polu stał jakiś pionek,
to następuje wzajemne "bicie" i oba pionki zostają wyeliminowane z gry.
Przegrywa gracz, który nie może wykonać żadnego ruchu.
Za każdym razem Bituś przygotowuje planszę (tzn. wybiera liczbę dodatnią ) oraz
wspaniałomyślnie oddaje pierwszy ruch Bajtusiowi.
Bituś jednak nie lubi przegrywać, więc postanowił wybierać zawsze taką planszę, na której
drugi gracz ma strategię wygrywającą. Tak jest np. dla plansz o długościach lub .
Nie chce jednak, by Bajtuś zaczął coś podejrzewać, więc za każdym razem musi wybrać
planszę innego rozmiaru.
Poprosił Cię zatem o pomoc. Napisz program, który dla danej liczby wypisze
-ty co do wielkości rozmiar planszy, na której drugi gracz ma strategię wygrywającą.
Wejście
W jedynym wierszu wejścia znajduje się jedna liczba całkowita
().
Wyjście
W jedynym wierszu wyjścia należy wypisać jedną liczbę całkowitą równą rozmiarowi
-tej co do wielkości planszy gwarantującej zwycięstwo drugiemu graczowi.
Przykład
Dla danych wejściowych:
2
poprawną odpowiedzią jest:
10
Autor zadania: Tomasz Idziaszek.