Задача №111610. Логическая схема
Булевой функцией называется функция из {0, 1}n в {0, 1}. Булеву функцию можно задать таблицей истинности —
значениями функции на области определения. Например, можно рассмотреть функции «И», «ИЛИ» и «НЕ», которые мы будем обозначать 
,
и ≠ g соответственно. Выпишем их таблицы истинности:
| \(x\) | \(y\) | \(x \wedge y\) | \(x \vee y\) | \(\neg x\) |
| 0 | 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 0 |
Булеву функцию f можно задать схемой. Схему можно определить так. Пусть имеется n булевых переменных x1, x2, ... xn, называемых входами. Пусть также имеется некоторое число булевых переменных y1, y2, ..., ym, называемых проводниками. Пусть для каждого проводника схемы задана функция «И», «ИЛИ» или «НЕ», выражающая его значение через другие проводники и входы. При этом требуется, чтобы среди зависимостей не было циклических. Кроме того, среди проводников выделен один, который называется выходом. Его значение является функцией от x1, x2, ..., xn, которая нас интересует. Размером схемы называется число m (количество проводников).
Вам задана булева функция f. Нужно построить схему как можно меньшего размера, которая вычисляет f. Отметим, что достигать оптимального размера не требуется.
Входные файлы к этой задаче являются открытыми; их можно найти здесь.
Первая строка входных данных содержит n — количество переменных. Следующая строка содержит 2n значений функции на входах, упорядоченных лексикографически (например, для n = 2 значения будут записаны в таком порядке: f(0, 0), f(0, 1), f(1, 0) и f(1, 1)).
Решением задачи считается набор выходных файлов, соответствующих входным, запакованный архиватором zip. Архив должен содержать по одному файлу XX.out на каждый входной файл XX (без расширения) или на любую часть этих файлов, и не должен содержать никаких других файлов и папок.
Каждый выходной файл должен содержать описание найденной вами схемы для соответствующей функции. Первая строка должна содержать размер схемы s. Далее в s строках должны содержаться описания проводников. В последней из этих s строк должно содержаться описание выхода схемы.
Теперь объясним, как должно выглядеть описание проводника. Описание должно начинаться с операции, которая соответствует данному проводнику. «НЕ» обозначается «!», «И» обозначается «&», а «ИЛИ» — «|». Далее в строке должны находиться аргументы операции: один для «НЕ» и два для «ИЛИ» и «И». Каждый аргумент соответствует либо проводнику, либо входу. В первом случае вы должны выводить номер проводника, во втором — номер входа, умноженный на -1. Номера проводников, от которых зависит данный, должны быть строго меньше его номера (для гарантии отсутствия циклических зависимостей).
Проводники и входы нумеруются с единицы.
3
01101001
14
! -1
! -2
! -3
& 1 2
& 4 -3
& 1 -2
& 6 3
& -1 2
& 8 3
& -1 -2
& 10 -3
| 5 7
| 12 9
| 13 11
Оценка за решение — это сумма оценок за каждый тест. Оценка за отдельный тест вычисляется следующим образом. Максимальный балл за тест, который можно получить, равен 10. Если ваша схема некорректная, не вычисляет требуемую функцию или содержит больше 1 000 000 проводников, то вы получите 0 баллов.
В таблице указано количество баллов, которое получит схема в зависимости от количества проводников в ней. В первом столбце записано количество баллов, во втором и третьем — минимальное и максимальное количество проводников, соответственно.
| 10 | 0 | 50000 |
| 9 | 50001 | 60000 |
| 8 | 60001 | 80000 |
| 7 | 80001 | 100000 |
| 6 | 100001 | 150000 |
| 5 | 150001 | 400000 |
| 4 | 400001 | 600000 |
| 3 | 600001 | 700000 |
| 2 | 700001 | 800000 |
| 1 | 800001 | 1000000 |
| 0 | 1000001 | \(\infty\) |