Bramki
Limit pamięci: 32 MB
Dany jest układ złożony z bramek.
Bramki są ponumerowane od do .
Każda bramka posiada pewną liczbę wejść i jedno wyjście.
Wejścia i wyjścia mogą przyjmować stany , lub .
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 i są specjalne - nie posiadają wejść i zawsze
przyjmują określone stany na wyjściu: dla bramki o numerze ,
dla bramki o numerze .
Mówimy, że stan wyjścia bramki (krótko: stan bramki) jest poprawny,
jeżeli:
-
jest równy i bramka ma więcej wejść w stanie niż w
stanie .
-
jest równy i bramka ma tyle samo wejść w stanie
co w stanie .
-
jest równy i bramka ma więcej wejść w stanie niż
w stanie .
-
dana bramka jest specjalna, tzn. ma numer lub ,
i jej stan jest równy odpowiednio lub .
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 ,
.
Kolejne wierszy zawiera opisy połączeń bramek.
Wiersz nr opisuje połączenia łączące wyjścia bramek z wejściami
bramki nr .
W wierszu tym znajduje się liczba wejść bramki nr ,
po której następuje numerów bramek, .
Są to numery bramek, których wyjścia są połączone z kolejnymi
wejściami bramki nr .
Liczby w wierszach są pooddzielane pojedynczymi odstępami.
Łączna liczba wszystkich wejść bramek nie przekracza .
Wyjście
Twój program powinien wypisać na standardowe wyjście wierszy.
W zależności od stanu bramki numer , -ty wiersz powinien
zawierać:
-
0 - jeżeli stan bramki jest zdeterminowany i wynosi ,
-
1/2 - jeżeli stan bramki jest zdeterminowany i wynosi
,
-
1 - jeżeli stan bramki jest zdeterminowany i wynosi ,
-
? (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
poprawną odpowiedzią jest:
0
1
1/2
?
?
Autor zadania: Bartosz Walczak.