Olimpiada Informatyczna

III Olimpiada Informatyczna 1995/96

Zadanie: HAZ

Autor: Wojciech Plandowski

Hazard

Zawody II stopnia

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

Maszyna hazardowa składa się z n generatorów liczb: G₁, ..., G_n, gdzie 1 <= n <= 1000. Generator G_i może generować liczby tylko z ustalonego zbioru S_i zawierającego się w {1,..., n}, lub liczbę zero oznaczającą koniec gry. Zbiór S_i może być zbiorem pustym. Niech k_i oznacza liczbę elementów zbioru S_i. Suma liczb k_i dla wszystkich i = 1,..., n nie może przekroczyć 12000.

Pierwsze uruchomienie generatora G_i powoduje wygenerowanie losowej liczby ze zbioru S_i. Kolejne uruchomienie powoduje wygenerowanie losowej liczby ze zbioru S_i, która nie została jeszcze wylosowana przez ten generator. Jeśli takiej liczby nie ma, G_i generuje liczbę zero.

Maszyna zaczyna działanie od uruchomienia generatora G₁. Następnie, generatory są uruchamiane zgodnie z zasadą, że jeśli uruchomiony generator wygenerował liczbę dodatnią r, to następnym uruchomionym generatorem jest G_r. Jeśli ostatnio wygenerowana liczba jest zerem, to maszyna się zatrzymuje.

Maszyna ponosi porażkę, gdy generator G_n wygeneruje zero oraz wszystkie generatory wygenerowały wszystkie liczby ze swoich zbiorów.

Maszyna jest dobrze skonstruowana, gdy istnieje kończąca się zerem sekwencja kolejno generowanych liczb nie prowadząca do porażki maszyny.

Zadanie

Napisz program, który:

wczytuje z pliku tekstowego HAZ.IN opis maszyny, tzn. liczbę generatorów n, liczby k_i i zbiory S_i,
bada, czy maszyna opisana w pliku wejściowym jest dobrze skonstruowana, jeśli nie, zapisuje w pliku tekstowym HAZ.OUT jedno słowo NIE, a w przeciwnym przypadku kończącą się zerem sekwencję kolejno generowanych liczb nie prowadzącą do porażki maszyny.

Wejście

W pierwszym wierszu pliku tekstowego HAZ.IN jest zapisana jedna liczba całkowita dodatnia n <= 1000. Jest to liczba wszystkich generatorów. W (i + 1)-szym wierszu (dla i = 1,..., n) jest liczba k_i i po niej wszystkie elementy zbioru S_i w dowolnej kolejności. Kolejne liczby w każdym wierszu są pooddzielane pojedynczymi odstępami.

Wyjście

W pliku tekstowym HAZ.OUT należy zapisać jedno słowo NIE (jeśli maszyna nie jest dobrze skonstruowana) albo, w jednym wierszu, odpowiedni skończony ciąg liczb pooddzielanych pojedynczymi odstępami.

Przykłady

Dla pliku HAZ.IN:
2
2 1 2
1 2

poprawnym rozwiązaniem jest plik HAZ.OUT:
2 2 0

Dla pliku HAZ.IN:
2
1 2
0

poprawnym rozwiązaniem jest plik HAZ.OUT:
NIE

Twój program powinien szukać pliku HAZ.IN w katalogu bieżącym i tworzyć plik HAZ.OUT również w bieżącym katalogu. Plik zawierający napisany przez Ciebie program w postaci źródłowej powinien mieć nazwę HAZ.???, gdzie zamiast ??? należy wpisać co najwyżej trzyliterowy skrót nazwy użytego języka programowania. Ten sam program w postaci wykonalnej powinien być zapisany w pliku HAZ.EXE