XI Olimpiada Informatyczna 2003/2004
|
Zawody II stopnia |
Plik źródłowy: | bra.xxx (xxx=pas,c,cpp) |
Limit pamięci: | 32 MB |
Alternatywne formaty: PostScript | PDF
Dany jest układ złożony z n bramek. Bramki są ponumerowane od 0 do n-1. Każda bramka posiada pewną liczbę wejść i jedno wyjście. Wejścia i wyjścia mogą przyjmować stany 0, 1 lub 1/2. Każde wejście jest połączone z dokładnie jednym wyjściem pewnej bramki. Stan wejścia jest równy stanowi wyjścia, z którym jest ono połączone. Każde wyjście może być połączone z dowolną liczbą wejść. Bramki o numerach 0 i 1 są specjalne --- nie posiadają wejść i zawsze przyjmują określone stany na wyjściu: 0 dla bramki o numerze 0, 1 dla bramki o numerze 1. Mówimy, że stan wyjścia bramki (krótko: stan bramki) jest "poprawny", jeżeli:
Napisz program, który:
Pierwszy wiersz standardowego wejścia zawiera liczbę bramek n, 2 <= n <= 10,000. Kolejne n-2 wierszy zawiera opisy połączeń bramek. Wiersz nr i opisuje połączenia łączące wyjścia bramek z wejściami bramki nr i. W wierszu tym znajduje się liczba k_i wejść bramki nr i, po której następuje k_i numerów bramek, k_i >= 1. Są to numery bramek, których wyjścia są połączone z kolejnymi wejściami bramki nr i. Liczby w wierszach są pooddzielane pojedynczymi odstępami. Łączna liczba wszystkich wejść bramek nie przekracza 200,000.
Dla danych wejściowych:
5 2 0 1 2 4 2 2 2 4
prawidłową odpowiedzią jest:
0 1 1/2 ? ?