Polish version    English version  
  Historia OI -> X OI 2002/2003 -> Zadania


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

Zadanie: ska
Autor: Adam Borowski
Skarb

Zawody III stopnia, dzień pierwszy  
Plik źródłowy: ska.xxx (xxx=pas,c,cpp)

Alternatywne formaty: PostScript | PDF

Król Bajtazar ukrywał w swym zamku skarb, a miejsce jego ukrycia trzymał w tajemnicy. Kiedy jednak wyruszał na wojnę bał się, że może zginąć i skarb przepadnie. Wybrał więc zaufanych strażników i każdemu powierzył część informacji potrzebnych do odnalezienia skarbu. Następnie rozkazał strażnikom zejść do lochów rozciągających się pod zamkiem (każdemu w inne miejsce) i chodzić po lochach metodą prawej ręki. Lochy to podziemne komnaty połączone korytarzami. Korytarze nie przecinają się poza komnatami. Korytarz może przebiegać pod innymi korytarzami. Nie ma korytarzy prowadzących do tej samej komnaty, z której wychodzą. Metoda prawej ręki polega na tym, że strażnik po wejściu do komnaty wychodzi z niej pierwszym korytarzem po prawej stronie. Strażnicy rozpoczynają wędrówkę przy wejściach do korytarzy, zatem może się zdarzyć, że wielu strażników zaczyna wędrówkę wychodząc z tej samej komnaty, jeśli tylko ruszają różnymi korytarzami.

Król wie, że dopóki nie powróci z wojny lub nie polegnie, każdy ze strażników będzie wiernie wykonywał jego rozkazy. Jest jednak świadom, że gdy tylko dwóch (lub więcej) strażników spotka się w komnacie, to nie omieszka wymienić się wszystkimi posiadanymi informacjami dotyczącymi skarbu. Strażnicy nie są samolubni i wymieniają informacje, nawet, jeśli któryś z nich nie dowie się w ten sposób niczego nowego. Jeśli strażnicy rozpoczynają wędrówkę w tej samej komnacie, to od razu wymieniają się informacjami, które początkowo znają. Gdy jednak strażnicy mijają się w korytarzach, to nie rozmawiają ze sobą.

Król zastanawia się, czy gdy wróci szczęśliwie z wojny, skarb będzie nadal bezpieczny. Chce on wiedzieć, którzy strażnicy mogą poznać wszystkie informacje potrzebne do odnalezienia skarbu.

Zadanie

Napisz program, który:

  • wczyta ze standardowego wejścia opis lochów, początkowe położenie strażników, komnaty, do których pójdą najpierw, oraz informacje dotyczące skarbu, jakie każdy ze strażników początkowo zna,
  • wyznaczy strażników, którzy mogą kiedyś poznać wszystkie informacje potrzebne do odnalezienia skarbu,
  • wypisze numery tych strażników na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia zapisana jest jedna liczba całkowita n. Jest to liczba komnat w lochach, 2 <= n <= 100. Komnaty są ponumerowane od 1 do n. W kolejnych n wierszach opisane są korytarze łączące komnaty. W wierszu i + 1 opisane są korytarze wychodzące z komnaty nr i, w kolejności zgodnej z ruchem wskazówek zegara. W każdym z tych wierszy znajdują się liczby całkowite pooddzielane pojedynczymi odstępami. Pierwsza z tych liczb, ki, to liczba korytarzy wychodzących z komnaty nr i, 1 <= ki <= n - 1. Dalej w tym samym wierszu zapisanych jest 2ki liczb całkowitych - każdy z wychodzących korytarzy jest opisany dwiema liczbami całkowitymi. Pierwsza z liczb opisujących korytarz to numer komnaty, do której on prowadzi. Druga z tych liczb to jego długość, liczba całkowita z zakresu od 1 do 100. Korytarze są dwukierunkowe, tzn. jeżeli z komnaty a wychodzi korytarz długości l prowadzący do komnaty b, to z komnaty b wychodzi korytarz długości l prowadzący do komnaty a. Każda para komnat może być połączona co najwyżej jednym korytarzem. Strażnik potrzebuje na przejście korytarzem dokładnie tyle czasu, ile wynosi jego długość. Zakładamy, że czas spędzany przez strażników w komnatach jest pomijalny.

W wierszu n + 2 zapisane są dwie liczby całkowite k i l, 1 <= k <= 100, 1 <= l <= 100, gdzie k to liczba strażników, a l to liczba informacji potrzebnych do odnalezienia skarbu. Strażnicy są ponumerowani od 1 do k. Informacje dotyczące skarbu są ponumerowane od 1 do l. W kolejnych k wierszach opisani są strażnicy, w wierszu i + n + 2 opisany jest strażnik nr i. W każdym z tych wierszy zapisane są liczby całkowite pooddzielane pojedynczymi odstępami. Pierwsza liczba w wierszu to numer komnaty, w której początkowo znajduje się strażnik. Druga liczba to numer komnaty, do której strażnik ruszy jako pierwszej. Trzecia liczba, mi, to liczba informacji dotyczących skarbu, które strażnik nr i początkowo zna, 0 <= mi <= l. Dalej w wierszu znajduje się mi liczb całkowitych - numery informacji znanych początkowo strażnikowi nr i.

Wyjście

W pierwszym wierszu standardowego wyjścia Twój program powinien wypisać jedną liczbę całkowitą - liczbę strażników, którzy mogą kiedyś poznać wszystkie informacje potrzebne do odnalezienia skarbu. W następnych wierszach powinny znaleźć się uporządkowane rosnąco numery tych strażników, po jednym w wierszu.

Przykład

Dla danych wejściowych:

4
3 2 3 3 4 4 1
2 1 3 3 1
3 4 3 1 4 2 1
2 1 1 3 3
3 4
1 4 2 2 3
3 1 2 1 2
3 4 2 3 4

poprawnym wynikiem jest:

2
2
3

przykład




Wersja do druku