Polish version    English version  
  Historia OI -> XI OI 2003/2004 -> Zadania


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
Terminarz
Zadania
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
II Etap
III Etap
Przepisy
Dla zawodnikow
Przydatne zasoby
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
XI Olimpiada Informatyczna 2003/2004

Zadanie: gra

Gra

Zawody I stopnia  
Plik źródłowy: gra.xxx (xxx=pas,c,cpp)
Limit pamięci: 32 MB

Rozważmy grę na prostokątnej planszy m x 1 złożonej z m jednostkowych kwadratów ponumerowanych kolejno od l do m. Na planszy ustawionych jest n pionków, każdy na innym polu, przy czym żaden pionek nie znajduje się na polu o numerze m. 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 m.

Dla przykładu z rysunku (m = 7), gracz może wykonać ruch z pola 2 na 4, z pola 3 na 4 lub z pola 6 na 7. Ten ostatni ruch kończy grę.

Przykład

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 m i n (2 <= m <= 109, 1 <= n <= 106, n < m) oddzielone pojedynczym odstępem. Drugi wiersz zawiera n 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

prawidłową odpowiedzią jest:

1

Dla danych wejściowych:

5 2
2 3

prawidłową odpowiedzią jest:

0



Wersja do druku