Matemagik
Konkurs nr 18
Data konkursu: 2013-05-08
Liczba uczestników: 14
Klucz: klucz dostępny po zalogowaniu
Zadanie
Zadanie
Jacek i Placek grają w grę, której celem jest zebrać jak najwięcej monet z pewnej ustalonej ich liczby $n$.
Gracze na przemian biorą pewną dodatnią liczbę monet, ale nie więcej niż z góry ustaloną liczbę $k$.
Monety są zbierane po stronie każdego gracza. Zawodnik, który weźmie ostanie monety ze stolika zatrzymuje wszystkie dotąd zebrane monety
dla siebie, a gra toczona jest dalej od nowa na monetach gracza, który przegrał i to on teraz rozpoczyna. Gra toczy się tak długo, aż wszystkie monety zostaną rozdzielone.
Jacek rozpoczyna grę i obaj grają optymalnie.
Wyznacz liczbę monet jaką uzbiera Jacek podczas gry.
Każdy test to jedna gra. Każda gra to dwie liczby całkowite $n$ i $k$, gdzie $n$ to liczba monet, a $k$ to ustalona górna granica.
Wyjaśnienie na przykładzie: $5$ $2$
Na stole leży 5 monet, gracze mogą zabrać jednowarozo co najwyżej 2 monety.
Optymalna strategia:
J: 2
P: 2
J: 1
Placek przegrał rozgrywkę, Jacek zabiera 3 monety, a gra toczy się dalej z 2 monetami Placka, który teraz zaczyna:
P: 2
Koniec gry.
Wynik J: 3, P: 2.
Przykłady
5 2 (wynik: 3)
5 3 (wynik: 3)
10 3 (wynik: 7)
Testy:
6 2
6 3
7 3
8 5
10 3
12 4
20 7
30 7
50 11
99 13