9538. Kot pucybut [KOTYYYYY]

Zadanie:
https://pl.spoj.com/problems/KOTYYYYY

Skrócony opis problemu:

Stoją sobie 2 koty na prostej podzielonej na jednostki. Każdy z nich może się poruszyć o 1 lub 2 pola w kierunku przeciwnika. Ruchy wykonują naprzemiennie. Wygrywa kot, który uniemożliwi przeciwnikowi ruch - nie można przesunąć się na zajęte pole oraz przeskoczyć przeciwnika. Który kot wygra, zakładając, że oba grają optymalnie?

Rozwiązanie:

Załóżmy, że zaczyna zawsze kot po lewej stronie. W zadaniu to jeden dodatkowy if. Jest to zadanie z teorii gier. Jednym rozwiązaniem jest rozpisanie sobie kilkunastu przypadków i zauważenie zależności. My jednak rozwiążemy to porządnie.

Możemy to zrobić określając pozycje przegrywające i wygrywające, a następnie sprawdzenie, na której znajduje się lewy kot. Pozycja wygrywająca to taka pozycja, że jeśli gracz będzie z niej zaczynał i grał optymalnie to wygra. Pozycja przegrywająca to taka, na której kot nie może się ruszyć lub jakikolwiek ruch by nie wykonał to przejdzie na pozycję wygrywającą (bo jeśli przejdzie na pozycję wygrywającą i będzie kolej przeciwnika, to wg poprzedniej definicji przeciwnik wygra).

Określmy zatem pierwsze pozycje. Na pewno jeśli staniemy tuż przy przeciwniku, to przegraliśmy. Załóżmy więc, że my jesteśmy na pozycji $x$, a przeciwnik na pozycji $y$ ($x < y$). Pozycja $y-1$ jest zatem przegrywająca. Jeśli uda nam się doprowadzić przeciwnika do tej pozycji to wygramy. Możemy się poruszać o 1 lub 2 pola, więc pozycje $y-2$ oraz $y-3$ są wygrywające, gdyż możemy skoczyć na pole $y-1$. Pójdźmy dalej. Pozycja $y-4$ jest przegrywająca, gdyż ile byśmy nie poszli dalej to i tak skończymy na pozycji wygrywającej. Jeśli kończymy na pozycji wygrywającej to znaczy, że przegramy, gdyż przeciwnik zaczyna z pozycji wygrywającej. $y-5$ i $y-6$ są znów wygrywające, bo skaczemy na pozycję przegrywającą.

Poniższa ilustracja pokazuje pozycje przegrywające i wygrywające dla odległości między kotami równej 16.

Jak widzimy, w tym przypadku kot po lewej stronie jest na pozycji wygrywającej.

Jeśli zatem odległość między kotami (włączając koty) daje resztę z dzielenia przez 3 - 2, to kot zaczynający przegra. Tak więc dla odległości: 2, 5, 8, 11, 14, itd. kot starszy (bo ten zaczyna) przegra.

Złożoność: $O(1)$. Nie trzeba tworzyć liniowo powyższej tablicy, jako że widać zależność w niej występującą.