Gra
Limit pamięci: 32 MB
Rozważmy grę na prostokątnej planszy złożonej
z jednostkowych kwadratów ponumerowanych kolejno od do .
Na planszy ustawionych jest pionków, każdy na innym polu, przy
czym żaden pionek nie znajduje się na polu o numerze .
Pojedynczy ruch w grze polega na przestawieniu dowolnie wybranego
pionka na pierwsze wolne pole o większym
numerze.
Dwaj gracze wykonują na zmianę po jednym ruchu.
Wygrywa ten, który postawi pionek na ostatnim polu,
tzn. na polu o numerze .
Dla przykładu z rysunku (), gracz
może wykonać ruch z pola na , z pola na lub z pola
na .
Ten ostatni ruch kończy grę.
Mówimy, że ruch gracza jest wygrywający, jeżeli po jego wykonaniu
gracz ten może wygrać grę niezależnie
od tego, jakie ruchy będzie wykonywał jego przeciwnik.
Zadanie
Napisz program, który:
-
wczyta ze standardowego wejścia rozmiar planszy i początkowe
rozstawienie pionków,
-
wyznaczy liczbę różnych ruchów wygrywających, jakie w zadanej
sytuacji początkowej ma do wyboru gracz rozpoczynający grę,
-
wypisze wynik na standardowe wyjście.
Wejście
Pierwszy wiersz wejścia zawiera dwie liczby całkowite
i (, , )
oddzielone pojedynczym odstępem.
Drugi wiersz zawiera rosnących numerów pól, na
których znajdują się pionki. Liczby w wierszu są
pooddzielane pojedynczymi odstępami.
Wyjście
Pierwszy i jedyny wiersz wyjścia powinien zawierać liczbę różnych
ruchów wygrywających, jakie może wykonać w zadanej sytuacji początkowej
gracz rozpoczynający grę.
Przykład
Dla danych wejściowych:
5 2
1 3
poprawną odpowiedzią jest:
1
a dla danych wejściowych:
5 2
2 3
poprawnym wynikiem jest:
0
Autor zadania: Bartosz Walczak.