Polish version    English version  
 


 Aktualności
 O olimpiadzie
 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
XI Olimpiada Informatyczna 2003/2004

Zadanie: bra

Bramki

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:

  • a) jest równy 0 i bramka ma więcej wejść w stanie 0 niż w stanie 1.
  • b) jest równy 1/2 i bramka ma tyle samo wejść w stanie 0 co w stanie 1.
  • c) jest równy 1 i bramka ma więcej wejść w stanie 1 niż w stanie 0.
  • d) dana bramka jest specjalna, tzn. ma numer 0 lub 1, i jej stan jest równy odpowiednio 0 lub 1.
Mówimy, że stan układu jest "poprawny", jeżeli stan każdej z bramek jest poprawny. Mówimy, że stan bramki jest "zdeterminowany", jeżeli w każdym poprawnym stanie układu bramka ta przyjmuje ten sam stan.

Zadanie

Napisz program, który:

  • Wczyta z wejścia opis układu bramek.
  • Dla każdej bramki sprawdzi, czy jej stan jest zdeterminowany i jeżeli tak, to wyznaczy go.
  • Wypisze wyznaczone stany bramek na wyjście.

Wejście

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.

Wyjście

Twój program powinien wypisać na standardowe wyjście n wierszy. W zależności od stanu bramki numer i-1, i-ty wiersz powinien zawierać:
  • 0 --- jeżeli stan bramki jest zdeterminowany i wynosi 0,
  • 1/2 --- jeżeli stan bramki jest zdeterminowany i wynosi 1/2,
  • 1 --- jeżeli stan bramki jest zdeterminowany i wynosi 1,
  • ? (znak zapytania) --- jeżeli stan bramki nie jest zdeterminowany.

Przykład

Dla danych wejściowych:


5
2 0 1
2 4 2
2 2 4

prawidłową odpowiedzią jest:

0
1
1/2
?
?



Wersja do druku