Solved by 143 users: ...
UserDateAttemptTimeCMSC
sb3ar`09 mar 2008`Ruby1500.9170
sb3ar`09 feb 2008`Ruby1400.8674
sb3ar`29 jan 2008`Ruby1300.8380
sb3ar`19 jan 2008`Ruby900.5588
fetetriste`05 may 2009`Ruby604.5191
fetetriste`05 may 2009`Ruby704.3092
WsemirZ`30 jan 2008`Ruby100.6094
zloy_mipt`28 sep 2008`Ruby100.6094
sb3ar`19 jan 2008`Ruby700.5595
abeaumont`24 feb 2011`Python205.86144
abeaumont`24 feb 2011`Python105.66145
david_it21`17 apr 2008`Ruby100.33172
asp`16 jul 2007`C++200.02229
asp`16 jul 2007`C++100.02231
Vladimir_Sitnikov`12 dec 2005`C++300.02238
Madiyar_Tktl`19 jan 2014`Python424.56238
Madiyar_Tktl`19 jan 2014`Python324.53240
fetetriste`21 jul 2007`Ruby202.19261
BobicZdoh`28 dec 2005`Python604.83303
 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.
• 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