<PREV Problem:
NEXT>
Solved by 143 users: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

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 220ms

SW soft NIX
ID = 23.20.166.68