| Когнитивные технологии 2025-2026. Финал |
|---|
| Закончено |
Это задача с открытыми тестами.
Пин построил игровой аппарат, в котором можно выиграть морковку. Для обеспечения честности он зафиксировал несколько псевдослучайных булевых функций, определяющих результат игры. Функция под номером $$$t$$$ задаётся от $$$n_t$$$ булевых переменных. Игра должна быть непредсказуемой и честной, поэтому функций не должен знать никто, кроме Пина и вас.
Чтобы скрыть реализацию от игроков, Пин при постройке автомата использует только $$$\mathrm{nand}$$$-компоненты. Каждый такой компонент принимает два входных бита и возвращает один бит в соответствии с таблицей ниже.
| a | b | a nand b |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Две булевы функции $$$f_1$$$ и $$$f_2$$$ называются эквивалентными, если $$$$$$ f_1(x_1, \dots, x_{n_t}) = f_2(x_1, \dots, x_{n_t}) $$$$$$ для любых значений переменных $$$x_1, x_2, \dots, x_{n_t} \in \{0, 1\}$$$.
Для каждого теста по заданному номеру $$$t$$$ постройте схему из $$$\mathrm{nand}$$$-компонент, которая будет задавать функцию, эквивалентную указанной в таблице. Количество использованных $$$\mathrm{nand}$$$-компонент не должно превышать заданный лимит, потому что вместимость гаража Пина конечна.
| Номер | $$$n_t$$$ | Функция | Лимит nand-компонент |
| 0 | 3 | $$$(x_1 | x_2) \& x_3$$$ | 20 |
| 1 | 2 | $$$(x_1 | x_2)$$$ | 3 |
| 2 | 4 | $$$ x_4 \oplus ((x_1 | x_2 | x_4) \& x_3) $$$ | 15 |
| 3 | 5 | $$$ x_1 \oplus x_2 \oplus x_4 \oplus (x_1 \& x_3) \oplus (x_2 \& x_5) \oplus (x_3 \& x_4 \& x_5) \oplus 1 $$$ | 25 |
| 4 | 6 | $$$ ((x_1 | x_2 | x_3) \& (x_2 | x_3 | x_5 | x_6)) \oplus (x_1 \& x_4)$$$ | 21 |
| 5 | 6 | $$$ (\neg(x_1 \& x_2) | x_3) \oplus ((x_4 \& x_5 \& x_6) | (x_4 \oplus x_6))$$$ | 14 |
| 6 | 8 | $$$ (x_1 \oplus x_3) | ((x_2 \& x_5) \oplus x_6) | ((x_3 | x_4 | x_5 | x_6 | x_7 | x_8) \oplus (x_2 \& x_6)) $$$ | 33 |
В единственной строке дано целое число $$$t$$$ ($$$0 \le t \le 6$$$) — номер функции, для которой необходимо построить схему.
Для функции под номером $$$t$$$ выведите в первой строке целое число $$$m_t$$$ — количество используемых $$$\mathrm{nand}$$$-компонент. Оно не должно превышать соответствующий лимит для функции.
В следующих $$$m_t$$$ строках выведите описание $$$\mathrm{nand}$$$-компонент в формате «$$$x\_a$$$ nand $$$x\_b$$$». Входные переменные функции под номером $$$t$$$ заданы переменными $$$x\_1, x\_2, \ldots, x\_{n_t}$$$ и могут быть использованы в качестве входных битов для $$$\mathrm{nand}$$$-компонент.
Все $$$\mathrm{nand}$$$-компоненты исполняются последовательно. Результат выполнения каждого компонента записывается в переменную с минимальным неиспользованным номером. Результатом всех вычислений является результат выполнения последнего компонента.
0
5 x_1 nand x_1 x_2 nand x_2 x_4 nand x_5 x_6 nand x_3 x_7 nand x_7
Ниже представлены таблицы истинности для битовых операций, используемых в условии.
| a | b | a nand b | a $$$\&$$$ b | a | b | $$$\neg$$$ a | a $$$\oplus$$$ b |
| 0 | 0 | 1 | 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 | 0 | 0 |
