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
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: 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




Wersja do druku