Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

BFN3 - Piotruś na Lekcji Logiki

Ulubionymi zajęciami Piotrusia była logika, na której mógł się wreszcie poczuć spełniony. Na zajęciach Piotruś usłyszał ciekawy problem dotyczący spełnialności...

Formuła logiczna jest spełnialna wtedy i tylko wtedy, gdy jej zaprzeczenie nie jest tautologią, czyli formuła zawsze prawdziwą (dla dowolnych podstawień wartości logicznych). Napisz program, który rozstrzyga, czy podana na wejściu formuła logiczna jest spełnialna. Przyjmujemy, że pojawiające się na wejściu formuły mają postać

(x1 \/ x2) /\ (x3 \/ x4) /\ … /\ (x2r-1 \/ x2r),

gdzie r <= 100, a każde z wyrażeń xi należy do zbioru {p1, p2, …, p99, ~p1, ~p2, …, ~p99}.

Wejście

Na wejście programu podana zostanie pewna liczba formuł logicznych. Formuła (x1 \/ x2) /\ (x3 \/ x4) /\ … /\ (x2r-1 \/ x2r) pojawi się na wejściu w postaci

(s1s2)(s3s4) … (s2r-1s2r),

gdzie si = +n, gdy xi = pn i si = -n, gdy xi = ~pn. Dla przykładu formuła (p5 \/ ~p3) /\ (~p20 \/ ~p70) pojawi się na wejściu jako napis (+05-03)(-20-70). Poszczególne formuły rozdzielone zostaną znakami nowej linii, tzn. każda linia zawierać będzie dokładnie jedną formułę.

Wyjście

Na wyjściu ma się pojawić ciąg zerojedynkowy, który na i-tej pozycji ma zawierać binarną odpowiedź na to, czy i-ta pobrana z wejścia formuła jest spełnialna (0 - nie jest, 1 - jest).

Przykład

Wejście:

(+01-02)(+01+02)(-01+02)(-01-02)
(+05-03)(-20-70)
(+05+05)(+06-06)(+10-11)

Wyjście:

011

Dodane przez:mima
Data dodania:2005-05-08
Limit czasu wykonania programu:7s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
Pochodzenie:autor: Robert Janczewski

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.