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