При реализации схемы для робота вы обнаружили некоторые аномалии. Существует $N = 128$ программ, пронумерованных от $0$ до $N-1$, которые может запускать робот. В нормальном режиме в любой момент времени должна работать только одна программа (из $N$ доступных). Однако по неизвестным причинам иногда одновременно запускаются ровно три программы. К счастью, как опытный программист, вы знаете, как справиться с этой ситуацией, и решили реализовать схему для обнаружения таких аномалий.
Сначала вы создаете $N$ входов. $i$-й вход равен $0$, если $i$-я программа не запущена, и $1$ в противном случае. Затем вы добавляете вентили (логические элементы), индексы которых нумеруются последовательно, начиная с $N$. Каждый вентиль может принимать определенное количество входов и выдавать один выход, равный $0$ или $1$. Входами $i$-го вентиля могут быть выходы любого вентиля с индексом меньше $i$ или любой из исходных $N$ входов.
Существует три типа вентилей:
NOT: принимает ровно один вход. Выход равен $1$, если вход равен $0$, и $0$ в противном случае.OR: принимает ровно два входа. Выход равен $0$, если оба входа равны $0$, и $1$ в противном случае.AND: принимает ровно два входа. Выход равен $1$, если оба входа равны $1$, и $0$ в противном случае.
Выход последнего вентиля должен быть равен $1$, если обнаружена аномалия (то есть если ровно три из первых $N$ входов равны $1$), и $0$, если ровно один из первых $N$ входов равен $1$.
Гарантируется, что количество единиц среди первых $N$ входов равно либо единице, либо трем.
Детали реализации
Вы должны записать в выходной файл описание корректной схемы для $\color{red}{N = 128}$.
Первая строка выходного файла должна содержать целое число, представляющее количество использованных вентилей.
Каждая из последующих строк должна соответствовать одному из трех форматов:
NOT in_1 OR in_1 in_2 AND in_1 in_2
Каждая строка добавляет вентиль NOT, OR или AND соответственно. Для NOT, in_1 — это индекс входа вентиля. Для OR и AND, in_1 и in_2 — это индексы входов вентиля. Индекс вентиля, добавленного в $i$-й строке после первой, равен $N-1 + i$.
Общее количество вентилей не должно превышать $1024$. Иными словами, общее количество строк в выходном файле не должно превышать $1025$.
Подзадачи
- (100 баллов) Дополнительные ограничения отсутствуют.
Оценка
Для каждой подзадачи, если существует случай, который схема не проходит, ваш балл будет равен $0$.
В противном случае, пусть $K$ — количество вентилей, использованных в схеме. Ваш балл будет равен $f(K) \times$ [балл за подзадачу], где:
$f(K) = \begin{cases} 0 & 1024 < K \\ 0.3 - 0.1 \times \frac {K - 384}{896} & 384 < K \le 1024 \\ 0.6 - 0.3 \times \frac {K - 256}{128} & 256 < K \le 384 \\ 1 - 0.40 \times \frac{K - 215}{41} & 215 < K \le 256 \\ 1 & K \le 215 \end{cases}$
Рисунок 1: График зависимости балла от K
Вы должны записать свое решение в выходной файл 1.out, затем сжать выходные файлы в один .zip-архив и отправить его.
Примеры
Входные данные 1
(input data)
Выходные данные 1
3 OR 0 1 OR 2 3 AND 4 5
Примечание
Рассмотрим упрощенную версию задачи с $N = 4$ (Обратите внимание, что вам нужно предоставить решение только для $N = 128$). Схема содержит: - вентиль $4$, который выдает $1$, если хотя бы один из входов $0$ или $1$ равен $1$; - вентиль $5$, который выдает $1$, если хотя бы один из входов $2$ или $3$ равен $1$; - вентиль $6$, который выдает $1$, если оба выхода вентилей $4$ и $5$ равны $1$. Можно проверить, что для всех возможных входных данных схема выдает правильный ответ.