| O olimpiadzie -> Zadania |  |
|
III Olimpiada Informatyczna 1995/96
|
|
Zadanie: HAZ
|
Autor: Wojciech Plandowski
|
| 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: G1, ..., Gn, gdzie 1 <= n <= 1000. Generator Gi może generować liczby tylko z ustalonego zbioru Si zawierającego się w {1,..., n}, lub liczbę zero oznaczającą koniec gry. Zbiór Si może być zbiorem pustym. Niech ki oznacza liczbę elementów zbioru Si. Suma liczb ki dla wszystkich i = 1,..., n nie może przekroczyć 12000.
Pierwsze uruchomienie generatora Gi powoduje wygenerowanie losowej liczby ze zbioru Si. Kolejne uruchomienie powoduje wygenerowanie losowej liczby ze zbioru Si, która nie została jeszcze wylosowana przez ten generator. Jeśli takiej liczby nie ma, Gi generuje liczbę zero.
Maszyna zaczyna działanie od uruchomienia generatora G1. Następnie, generatory są uruchamiane zgodnie z zasadą, że jeśli uruchomiony generator wygenerował liczbę dodatnią r, to następnym uruchomionym generatorem jest Gr. Jeśli ostatnio wygenerowana liczba jest zerem, to maszyna się zatrzymuje.
Maszyna ponosi porażkę, gdy generator Gn 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 ki i zbiory Si,
- 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 ki i po niej wszystkie elementy zbioru Si 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