Ja już zaczynam się przygotowywać. E złapałem jakieś zadanie i co jest grane? W czystym cpp to pisać czy mogę dodać powiedzmy bibliotekę Allegro? Jest wzmianka o grafice ale nie ma nic o bibliotece.
VIII Olimpiada Informatyczna 2000/2001
Zadanie: GRA
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
