Polish version    English version  
  O olimpiadzie -> Zadania


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

Zadanie: GRA
Autor: Marcin Jurdziński
Gra w zielone

Zawody I stopnia  
Plik źródłowy: GRA.??? (np. pas, c, cpp)
Plik wykonywalny: GRA.exe
Plik wejściowy: GRA.in
Plik wyjściowy: GRA.out

Gra w zielone jest grą dla dwóch graczy - nazwijmy ich Ania i Bolek - polegającą na przesuwania pionka po planszy.

Część pól planszy jest pokolorowana na zielono, a pozostałe są białe. Wszystkie pola są ponumerowane liczbami naturalnymi z zakresu 1...(a+b). Pola o numerach z zakresu 1...a należą do Ani, natomiast pola o numerach (a+1)...(a+b) należą do Bolka.

Dla każdego pola dany jest zbiór następników, zawierający te pola planszy, do których można z niego przejść w jednym ruchu. Zbiory te zostały tak dobrane, że z pola należącego do Ani można przejść w jednym ruchu tylko na pole należące do Bolka i odwrotnie. Wszystkie pola mają niepuste zbiory następników, a więc zawsze można wykonać ruch.

Na początku gry ustawiamy pionek na dowolnym polu początkowym P, a następnie gracze na przemian przestawiają pionek ze swojego pola na dowolny następnik tego pola - należący do przeciwnika. Grę rozpoczyna właściciel pola początkowego P. Gra kończy się w momencie, gdy pionek stanie po raz drugi na tym samym polu. Nazwijmy to pole Q. Jeśli w sekwencji ruchów od pierwszego zajęcia pola Q do powtórnego zajęcia pola Q pionek stanął przynajmniej raz na polu zielonym, to wygrywa Ania, w przeciwnym przypadku wygrywa Bolek. Powiemy, że Ania ma strategię wygrywającą dla danego pola początkowego P, jeśli istnieje metoda gwarantująca jej wygraną w rozgrywce zaczynającej się od tego pola, niezależnie od tego, jakie ruchy będzie wykonywał Bolek.

Zadanie

Napisz program, który:

  • wczyta z pliku tekstowego GRA.IN opis planszy do gry w zielone,
  • znajdzie zbiór pól planszy, dla których Ania ma strategię wygrywającą,
  • zapisze wynik w pliku tekstowym GRA.OUT.

Wejście

W pierwszym wierszu pliku tekstowego GRA.IN zapisane są dwie dodatnie liczby całkowite a, b oddzielone pojedynczym odstępem, oznaczające odpowiednio: liczbę pól należących do Ani i liczbę pól należących do Bolka. Liczby a, b spełniają warunek: 1 <= a+b <= 3000. W kolejnych a+b wierszach opisano pola planszy - najpierw pola należące do Ani, a następnie pola należące do Bolka. Wiersz o numerze i+1, dla 1 <= i <= a+b, zawiera na początku liczby całkowite z, k oddzielone pojedynczym odstępem, oznaczające odpowiednio kolor pola o numerze i (0 oznacza kolor biały, 1 - kolor zielony), oraz liczbę następników tego pola. Następnie w tym wierszu zapisane jest k liczb całkowitych (1 <= k < a+b), pooddzielanych pojedynczymi odstępami, będącymi numerami następników danego pola. Liczba pól zielonych na planszy nie przekracza 100. Suma liczb następników wszystkich pól na planszy nie przekracza 30000.

Wyjście

Pierwszy wiersz pliku tekstowego GRA.OUT powinien zawierać dokładnie jedną liczbę całkowitą l, oznaczającą liczbę pól, dla których Ania ma strategię wygrywającą. Następne l wierszy powinno zawierać numery tych pól zapisane w kolejności rosnącej - każda liczba powinna zostać zapisana w osobnym wierszu.

Przykład

Dla pliku wejściowego GRA.IN:

5 3
0 2 6 7
0 3 6 7 8
0 1 8
1 1 7
1 1 8
1 2 1 2
0 2 1 2
0 2 3 4 

poprawną odpowiedzią jest plik wyjściowy GRA.OUT:

5
1
2
4
6
7



Wersja do druku