|
Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Автор: Игорь Андрианов, ВоГТУ.
Сложность Гамма
Одной из классических задач теории вычислений является задача о
выполнимости булевых формул - можно ли подобрать такие значения переменных,
входящих в формулу, чтобы её значение стало истинным.
Будем записывать формулы, используя:
• имена входных переменных x1, x2, ..., xN;
• логические операции: AND - конъюнкция ("И"),
OR - дизъюнкция ("ИЛИ"), ~ (тильда) - инверсия ("НЕ");
• круглые скобки.
Например, формула x1 AND x2 AND x5
выполнима, поскольку она принимает истинное значение при x1=x2=x5=1.
Формула же (x1 OR x2) AND ~x1 AND ~x2 невыполнима, поскольку её значение равно нулю при любых комбинациях
переменных x1 и x2. Известно, что в общем виде эта задача является
NP-полной. Вам предлагается решить её для частного случая, когда формула
имеет вид:
(p1 OR p2) AND (p3 OR p4) AND ... AND (pi OR pj)
а в качестве каждого члена p выступает либо некоторая входная переменная
xi, либо её отрицание ~xi.
Ввод
В первой строке ввода содержится булева формула, записанная в вышеописанном
формате. Общее количество переменных N не превышает 100, длина
формулы не превышает 10 000 символов. Слова AND, OR отделяются от соседних
символов одним пробелом. Других пробелов в строке нет.
Вывод
Вывод должен содержать слово "YES", если формула выполнима, и
"NO" в противном случае.
|
Ввод
|
Вывод
|
(x1 OR x2) AND (~x1 OR ~x1) AND (~x2 OR ~x2)
|
NO
|
Для отправки решений необходимо выполнить вход.
|