<ПРЕД Задача:
СЛЕД>
Задачу решили 143 пользователя: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Тавтология

Time limit = 5 секунд(ы)

Memory limit = 16 Mb

Дано логическое выражение от булевых переменных x1, x2, .. xM, в котором
Нужно определить, является ли данное выражение тавтологией, то есть верно ли, что при любых значениях булевых переменных выражение правдиво.

Например, выражения

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

являются тафтологиями.

Вход В первой строчке дано число булевых переменных M, 0 < M < 11. Во второй строчке дано логическое выражение. Для записи выражения используются термы x1 x2 .. xM & | ( ) <пробел> Запись выражения корректна. Между термами может встречаться любое число пробелов (в том числе нулевое). Длина выражения не превосходит 1000 символов.

Выход Выведите в первой строчке YES или NO, в зависимости от того, является ли выражение тавтологией. Если не является, выведите те значения переменных, при которых это выражение обращается в ЛОЖЬ (M штук разделённых пробелом нулей или единиц; 1=ПРАВДА, 0=ЛОЖЬ).

Вход#1
1
x1 | !x1
Выход#1
YES

Вход#2
3
!(x1 & x2 &(x3|x1)) 
Выход#2
NO
1 1 0

Автор:
Фольклор, тесты и условие подготовил Ворожцов Артем
6 октября 2005

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


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

SW soft NIX
ID = 18.210.24.208