Задача A. Согласиться нельзя отказаться
Задачу добавил: alef
Успешно сдано решений: 3
Будущий программист Кеша Канарейкин сидел на лавочке перед входом в университет. Идти на пару по математической логике желания у него совершенно не возникало. Настроение у Кеши было определенно весенним, и хотелось думать о чем-нибудь хорошем и радостном. Например, о Кате Сушкиной из параллельной группы. В отношении Кати Кеша уже вторую неделю разрабатывал стратегический план под кодовым названием «Что делать?»
— Может, пригласить ее в кино? – размышлял он. – Но на какой фильм? Вот сейчас в кинотеатрах идет романтическая комедия «Свекла – капуста», девушкам такое, наверное, нравится. Только идет эта комедия не первый день, и Катя могла уже посмотреть ее. А если спросить ее, видела ли она фильм? Если нет, то пригласить на него, а если видела... Конечно, можно попробовать пригласить ее на боевик «Девяносто шестая глава». А вдруг боевики ей совсем не нравятся? Кстати, интересно, а любит ли она вообще в кино ходить…
Кеша обдумывал возможные вопросы и ответы – как построить разговор, чтобы результат был положительным. И тут ему пришла в голову интересная идея – каждый из его вопросов можно сформулировать в виде логического утверждения, которое либо истинно, либо ложно. Допустим, например, что утверждения «Катя любит ходить в кино» и «Катя не видела новую комедию» – истинны. Тогда конъюнкция этих утверждений тоже даст истину, и, по мнению Кеши, вполне можно надеяться, что Катя согласится пойти с ним в кино. Все может выглядеть и сложнее, например:
Неверно, что «Катя не видела фильм» или «Катя не смотрит фильмы повторно» и «Катя любит ходить в кино» (слово «неверно» соответствует логическому отрицанию).
Если первое утверждение истинно, второе – ложно, а третье – истинно, то, при обычном вычислении «слева направо с учетом приоритета операций» получается ответ «ложь». Но если первое и второе утверждения заключить в скобки, так чтобы операция «или» выполнялась первой, затем к ее результату применялось бы отрицание, и, наконец, выполняется операция «и», то итоговый результат будет истинным. Если утверждений больше, то может быть несколько способов расставить скобки так, чтобы ответ оказался «истиной». Конечно, математическая логика сильно отличается от женской. Но почему не попробовать заранее узнать, можно ли вообще получить положительный ответ?
Формат входного файла input.txt
Первая строка – целые числа K (1<=K<=5) и N (1<=N<=10). K – количество логических выражений, N – максимальное количество переменных, участвующих в одном выражении
Каждая из следующих K строк – логическое выражение, состоящее из имен переменных (не менее одного имени) и операторов and, or и not. Имена переменных имеют длину, не превосходящую 8 символов, могут начинаться с буквы, цифры или символа подчеркивания. Все буквы в именах – строчные латинские. Имена переменных и операторы отделяются друг от друга одним пробелом. Гарантируется, что каждая строка является корректным логическим выражением.
В каждой из следующих строк содержится по одному имени переменной, участвующей хотя бы в одном выражении, и – через пробел – ее значение: true или false. Каждая переменная определяется ровно одной строкой, даже если переменная встречается в выражении более одного раза.
Формат выходного файла output.txt
В выходном файле содержится K строк – по одной на каждое логическое выражение.
Каждая из этих строк содержит слово YES или NO, означающие соответственно возможность или невозможность изменить значение исходного выражения в результате расстановки скобок.
Пример входного файла
2 4
xx and bcd and y1 or _z
not _z and not y1
bcd false
_z true
xx true
y1 false
Пример выходного файла
YES
NO
Примечание.
Первое выражение без скобок приводит к результату true. Расстановка скобок следующим образом:
xx and bcd and (y1 or _z)
даст результат false
Единственная возможность «нетривиальной» расстановки скобок во втором выражении приводит к выражению:
not (_z and not y1)
что, как и в выражении без скобок, приведет к значению false