<PREV Problem:
NEXT>
Solved by 143 users: ...
UserDateAttemptTimeCMSC
sb3ar09 mar 2008Ruby1500.9170 
sb3ar09 feb 2008Ruby1400.8674 
sb3ar29 jan 2008Ruby1300.8380 
sb3ar19 jan 2008Ruby900.5588 
fetetriste05 may 2009Ruby604.5191 
fetetriste05 may 2009Ruby704.3092 
WsemirZ30 jan 2008Ruby100.6094 
zloy_mipt28 sep 2008Ruby100.6094 
sb3ar19 jan 2008Ruby700.5595 
abeaumont24 feb 2011Python205.86144 
abeaumont24 feb 2011Python105.66145 
david_it2117 apr 2008Ruby100.33172 
asp16 jul 2007C++200.02229 
asp16 jul 2007C++100.02231 
Vladimir_Sitnikov12 dec 2005C++300.02238 
Madiyar_Tktl19 jan 2014Python424.56238 
Madiyar_Tktl19 jan 2014Python324.53240 
fetetriste21 jul 2007Ruby202.19261 
BobicZdoh28 dec 2005Python604.83303 
Languages
C++
88
FPC
17
Kylix
13
Java
11
C
7
Ruby
5
Python
3
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

Tautology

Time limit = 5 second(s)

Memory limit = 16 Mb

You're given a boolean expression with variables x1, x2, .. xM.
You are to determine, whether the expression is a tautology, i.e. it is true for all possible xi

For instance, the following expressions are tautologies:

x1 | !x1,     x1 | (!x1 & !x3) | x3,     x1 & x2 | !x1 & !x2 | !x1 & x2 | x1 & !x2,

Input The first line contains the number of boolean variables M, 0 < M < 11. The second line contains boolean expression.
The expression is formed via following terms x1 x2 .. xM & | ( )
The expression is well-formed. Any terms might be separated via arbitrary number of spaces (including zero one).
The length of an expression does not exceed 1000 characters.

Output The first line should contain YES or NO, depending whether the expression is a true tautology. If it does not, output the values of xi, when the expression turns FALSE. (M zeroes or ones, 1=TRUE, 0=FALSE).

Input#1
1
x1 | !x1
Output#1
YES

Input#2
3
!(x1 & x2 &(x3|x1)) 
Output#2
NO
1 1 0

Author:
Folklore, tests and description by Artem Voroztsov
6 oct 2005

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 190ms

SW soft NIX
ID = 3.214.184.250