АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

174. Выполнимость

Ограничение времени: 1 сек.
Ограничение памяти:65536 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил debug

Одной из классических задач теории вычислений является задача о выполнимости булевых формул — можно ли подобрать такие значения переменных, входящих в формулу, чтобы её значение стало истинным.

Будем записывать формулы, используя:

* имена входных переменных 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" в противном случае.

Пример

STDIN

STDOUT

(x1 OR x2) AND (~x1 OR ~x1) AND (~x2 OR ~x2)

NO

 

 


Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи с соревнований / Межвузовские олимпиады / IX Межвузовская олимпиада 2006 /
173. C - Расстановка минусов 174. 175. E - Марсоход 176. F - Сообщение 177. G - Скобки
Учебные курсы / Архитектура компьютера /
174. 679. Декодирование Хэмминга 131. Сумма цифр
 
время генерации 0.094 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.