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.
• Unary NOT is denoted via ! and has the maximal priority.
• Operation AND is denoted via & (and has the next priority).
• Operation OR is denoted via | (and has the minimal priority).

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

 © acm.mipt DevGroupThe page was generated in 190ms