SZKOpuł
Przełącz się na inny konkurs Baza zadań Archiwum zadań konkursowych Portale
Pozostały 34224 dni 3 godziny 39 minut 16 sekund do końca Zadania z oficjalnych matur "Nowa formuła".
6%
polski ✓ English

Zadanie Bramki (bra)

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:

  1. jest równy i bramka ma więcej wejść w stanie niż w stanie .
  2. jest równy i bramka ma tyle samo wejść w stanie co w stanie .
  3. jest równy i bramka ma więcej wejść w stanie niż w stanie .
  4. 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.