| Codeforces Round 488 by NEAR (Div. 1) |
|---|
| Закончено |
Хибики и Дита влюблены друг в друга, но принадлежат обществам, которые находятся в продолжительном конфликте. В сложившейся ситуации Хибики пытается понять, являются ли его отношения с Дитой актом Любви или актом Предательства.
Хибики приготовил несколько бинарных параметров, на основе которых он будет принимать решение, и построил трехслойную логическую схему, где каждый слой состоит из одного или более логических вентилей. Каждый вентиль в схеме — это «or» (или), «and» (и), «nor» (не или) или «nand» (не и). Каждый вентиль в первом слое получает на вход ровно два входных параметра. Каждый вентиль во втором слое получает на вход ровно два выхода вентилей из первого слоя. Третий слой состоит из одного вентиля «or» (или), который получает на вход выходные значения всех вентилей второго слоя (иными словами, вся схема выдает 1 тогда и только тогда, когда хотя бы один вентиль во втором слое выдал 1).
Но есть одна проблема. Хибики хорошо знает, что когда человек влюблен, его способности мыслить логически очень сильно падают. В частности, хорошо известно, что если влюбленный человек выполняет в голове логическую схему, выход каждого вентиля вычисляется в значение, обратное тому, которое этот вентиль должен выдать. Например, вентили «or» (или) выдают 1 тогда и только тогда, когда оба входа нули, а «nand» (не и) выдает 1 тогда и только тогда, когда оба входа единицы, и так далее.
В частности, вентиль «or» (или) в третьем слое тоже выдает противоположный результат, что значит, что если Хибики влюблен, то схема выдает 1 тогда и только тогда, когда все вентили на втором слое выдали 0.
Хибики не может позволить любви повлиять на свое решение. Он хочет узнать, какое минимальное количество вентилей надо убрать во втором слое, чтобы результирующая схема для любого входа выдавала одинаковое значение когда Хибики влюблен и когда он не влюблен.
Первая строка содержит три целых числа $$$n$$$, $$$m$$$, $$$k$$$ ($$$2 \le n, m \le 50$$$; $$$1 \le k \le 50$$$) — количество входных параметров, количество вентилей в первом слое и количество вентилей во втором слое, соответственно.
Вторая строка содержит $$$m$$$ пар строк разделенных пробелами, описавающих первый слой. Первая строка в каждой паре описывает тип вентиля («and», «or», «nand» или «nor»), а вторая — какие входные параметры подаются на вход этому вентилю в формате строки из ровно $$$n$$$ символов, из которых ровно два (соответствующие параметрам, которые подаются на вход) равны «x», а остальные равны «.».
Третья строка содержит $$$k$$$ пар строк разделенных пробелами, описывающих второй слой в таком же формате, при этом строки, описывающие входные параметры каждого вентиля, имеют длину $$$m$$$ и соответствуют выходам вентилей первого слоя.
Выведите одно число — минимальное количество вентилей, которые надо убрать со второго слоя, чтобы результат вычисления схемы не зависел от того, влюблен Хибики или нет.
Если сколько бы вентилей не было убрано, схема продолжит зависеть от влюбленности Хибики, выведите $$$-1$$$.
2 2 2
and xx nand xx
and xx or xx
1
3 2 2
and xx. nor .xx
and xx nor xx
-1
4 4 5
nor x..x and ..xx and xx.. nand xx..
nand ..xx nor ..xx and xx.. nor ..xx or ..xx
2
В первом примере оба вентиля в первом слое получают на вход одни и те же параметры, но один вычисляет «and» а второй вычисляет «nand», и как следствие значения на их выходе всегда будут разные, не зависимо от того влюблен Хибики или нет. Во втором слое есть два вентиля – «or» и «and», получающие на вход эти два различных значения. Если Хибики не влюблен, «and» выдаст 0 а «or» выдаст 1 для любого входа, и «or» в третьем гейте выдаст 1. Если Хибики влюблен, «and» выдаст 1 а «or» выдаст 0 для любого входа, и «or» в третьем слое выдаст 0 0. Таким образом, если оставить оба вентиля во втором слое, результат работы схемы зависит от того, влюблен Хибики или нет. Однако, если убрать любой из двух вентилей, вывод схемы перестанет зависеть от влюбленности Хибики, поэтому ответ — 1.
Во втором примере сколько бы вентилей не было убрано во втором слое, результат работы схемы будет зависеть от влюбленности Хибики.
В третьем примере если Хибики оставит второй, третий и четвертый вентили, схема перестанет зависеть от того, влюблен Хибики или нет. Альтернативно, он может оставить первый и последний вентили. Для первого варианта надо убрать 2 вентиля, для второго — 3, таким образом первый вариант лучше, и ответ — 2.
