- A
- B
- C
- D
- E
- F
- G
- H
Булевые функции
Задача A. Бинарные отношения
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Дано число n и два бинарных отношения на множестве размера n. Для каждого из этих отношений определите, являются ли они рефлексивными, антирефлексивными, симметричными, антисимметричными и транзитивными, а так же найдите их композицию.
Входные данные
В первой строке содержится число n — размер носителя (1 ⩽ n ⩽ 100). В следующих n строках находится по n чисел — описание первого отношения. Если j-е число i-й строки равно 1, то пара (i, j) лежит в отношении, иначе эта пара не лежит в отношении. В следующих n строках находится описание второго отношения в таком же формате.
Выходные данные
Для каждого из пяти свойств из условия выведите в первой строке 1, если первое отношение обладает этим свойством, и 0 иначе. Во второй строке выведите описание второго отношения в таком же формате.
В следующих n строках выведите по n чисел — композицию двух отношений в таком же формате, что и во входных данных.
Примеры
Входные данные
3
0 1 0
0 0 1
1 0 0
1 1 0
0 1 1
1 0 1
Выходные данные
0 1 0 1 0
1 0 0 1 0
0 1 1
1 0 1
1 1 0
Решение
Задача B. Теорема Поста
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Вам даны n булевых функций, заданных таблицами истинности. Требуется проверить, является ли заданный набор функций полным.
Входные данные
В первой строке содержится одно целое число n — количество функций (1 ⩽ n ⩽ 1000).
В следующих n строках содержится описание функций. Первым в строке дано число si — количество аргументов очередной функции (0 ⩽ si ⩽ 5). Далее дана строка ai из 2^si символов 0 и 1, она описывает таблицу истинности. Функция возвращает aij, если ей на вход подать представление j в двоичной системе счисления. Порядок аргументов соответствует порядку от младших битов к старшим.
Выходные данные
В единственной строке выведите YES, если набор полон, и NO иначе.
Примеры
Входные данные
3
2 0111
2 0001
1 10
Выходные данные
YES
Входные данные
2
2 0110
1 01
Выходные данные
NO
Решение
Задача C. Схема из функциональных элементов
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Дана схема из функциональных элементов в порядке топологической сортировки (то есть листьяпеременные имеют минимальные номера, а корень схемы — максимальный). Вам предстоит определить ее глубину, а также таблицу истинности для всевозможных входных данных.
Входные данные
В первой строке указано натуральное число n — количество вершин в схеме (1 ⩽ n ⩽ 27). В следующих строках описано устройство схемы.
Элементы даны в порядке от первого до n-го. Каждый элемент описывается либо одной (если это переменная-лист), либо двумя строчками (если это функция). Все переменные различны. Первое целое число m в первой строчке из описания i-го элемента — количество входов для этого элемента (0 ⩽ m ⩽ 5) (если элемент — переменная, то m = 0). Далее в этой же строке перечислены m натуральных чисел — номера элементов, значения с которых подаются на вход i-му.
Если m > 0, то в следующей строке дано 2^m целых чисел a0, a1, … a[2^m − 1]. Где aj — ответ, который выдает i-й элемент, если на входы подать двоичное представление числа j (0 ⩽ aj ⩽ 1). Более старшим разрядам j соответствуют более ранние (с меньшими индексами) входы, в порядке, написанном в предыдущей строке.
Выходные данные
В первой строке выведите одно число — глубину данной схемы.
Назовем количество переменных-листьев k. В следующей строке выведите битовую строчку длины 2^k, где в позиции j будет число, выдаваемое схемой если на вход подается число j, старшим разрядам j соответствуют листы, имеющие меньшие индексы.
Примеры
Входные данные
5
0
0
2 1 2
1 1 0 1
0
2 3 4
1 0 0 1
Выходные данные
2
01011001
Замечание
Обозначим как ans[i] — число, которое получается в i-м элементе. Тогда в данном примере значения функций, например, для 3-го элемента означают
| ans[1] | ans[2] | ans[3] |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Решение
Задача D. Построение схемы из функциональных элементов
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Дана булева функция, заданная таблицей истинности. Постройте схему из функциональных элементов, реализующую эту функцию в базисе не, и и или.
Входные данные
В первой строке находится число n — количество переменных (2 ⩽ n ⩽ 10). Следующие 2^n строк имеют следующий вид: значения переменных x1, x2, …, xn и значение функции при этих переменных. Строки даны в возрастающем лексикографическом порядке значений переменных.
Выходные данные
В первой строке выведите число m — количество элементов в вашей схеме (включая n элементов, отвечающие за исходное значение переменных). Элементы с номерами с 1 до n соответствуют входным переменным _x1, x2, …, xn. В следующих m−n строках выведите описание каждого нового элемента в схеме. Описание элемента состоит из номера операции в этом элементе и номеров аргументов, которые подаются на вход этому элементу.
Операция не имеет номер 1, и имеет номер 2, или имеет номер 3.
На вход операции не должно быть подан один элемент, а всем остальным два. На вход можно подавать только элементы с меньшим номером. Результатом вычисления схемы считается значение последнего элемента.
Разрешается использовать не более 10^5 элементов. Гарантируется, что существует схема, подходящее под данное ограничение.
Примеры
Входные данные
3
000 0
001 0
010 0
011 0
100 1
101 0
110 1
111 1
Выходные данные
6
1 3
3 2 4
2 1 5
Замечание
Функцию из примера можно задать формулой x1 ∧ (x2 ∨ ¬x3). Ответ на пример — схема, реализующая эту формулу.
Решение
Задача E. Полином Жегалкина
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Дана таблица истинности. Найдите по ней коэффициенты полинома Жегалкина.
Входные данные
В первой строке содержится число n — количество переменных в функции (1 ⩽ n ⩽ 10). Следующие 2^n строчек имеют следующий вид: значения переменных x1, x2, …, xn и значение функции при этих переменных. Строки даны в лексикографически возрастающем порядке значений переменных.
Выходные данные
Вывести 2^n строчек в следующем формате: значения переменных, через пробел значение коэффициента полинома Жегалкина для этой записи. Порядок строк должен быть таким же, как и во входных данных.
Примеры
Входные данные
2
00 0
01 1
10 0
11 1
Выходные данные
00 0
01 1
10 0
11 0
Входные данные
2
00 1
01 0
10 0
11 1
Выходные данные
00 1
01 1
10 1
11 0
Решение
Задача F. Форма Хорна
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
В этой задаче задана булева функция в форме Хорна. Требуется проверить, является ли она тождественным нулем.
Входные данные
Первая строка содержит два натуральных числа n, k — количество литералов и дизъюнктов (скобок в формуле) соответственно (1 ⩽ n, k ⩽ 100).
Следующие k строк описывают дизъюнкт в следующем формате: n чисел xi ∈ {−1, 0, 1}.
xi = 1 — i-й литерал входит в дизъюнкт без отрицания.
xi = 0 — i-й литерал входит в дизъюнкт с отрицанием.
xi = −1 — i-й литерал не входит в дизъюнкт.
Выходные данные
Выведите YES (без кавычек), если функция — тождественный ноль. Иначе выведите NO (без кавычек).
Примеры
Входные данные
3 3
1 0 0 1 0
-1 0 1
Выходные данные
NO
Входные данные
1 2
1
0
Выходные данные
YES
Замечание
В первом примере формула выглядит следующим образом: (x1 ∨ x̅2) ∧ (x̅1 ∨ x2 ∨ x̅3) ∧ (x̅2 ∨ x3)
Второй пример: (x1) ∧ (x̅1)
Решение
Задача G. К или Д?
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Дано целое число n и n неотрицательных целых чисел. Требуется проверить, можно ли составить формулу, используя побитовые И (&), ИЛИ (|), НЕ (~), круглые скобки ((, )) и данные числа, чтобы ее результатом являлось число s. Если да, то выведите любую. Вместо самих чисел в формуле должны быть их порядковые номера во входных данных. Для лучшего понимания разберите тесты из условия.
Входные данные
На первой строке содержится целое число n (1 ⩽ n ⩽ 5).
Во второйnцелых чисел ai (0 ⩽ ai ⩽ 2^32 − 1).
В последней строке содержится ровно одно целое число s.
Выходные данные
Выведите формулу, описанную выше, или Impossible, если ответа не существует. Если ответов несколько, выведите любой из них.
Примеры
Входные данные
1
8
8
Выходные данные
1
Входные данные
2
48 83
68
Выходные данные
Impossible
Входные данные
2
20 8
8
Выходные данные
2& ~1
Входные данные
1
1
4294967295
Выходные данные
Impossible
Замечание
Коды символов в ASCII: & — 38, | — 124, ~ — 126, ( — 40, ) — 41.
Решение
Задача H. Штрих Шеффера
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Известно, что с помощью штриха Шеффера (отрицание конъюнкции) можно выразить любую булеву функцию. Таблица истинности штриха Шеффера приведена ниже:
| x | y | x|y |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Рассмотрим задачу сложения двух двоичных чисел A и B, каждое из которых состоит из N бит. Биты в числах A и B пронумерованы от 0 (младший разряд) до N − 1 (старший разряд). Сумму A и B всегда можно представить как N + 1-битное число. Назовем самый старший бит суммы (бит с номером N ) битом переполнения.
Вам нужно построить булеву формулу, вычисляющую значение бита переполнения для произвольных N-битных чисел A и B, используя только штрих Шеффера. Формула строится по следующим правилам:
Ai— формула, равная значению i-го бита числаA.Bi— формула, равная значению i-го бита числаB.(x|y)— формула, обозначающая применение штриха Шеффера к x и y, где x и y — некоторые формулы.
Индекс i в формулах для битов чисел A и _B_записывайте десятичным числом без ведущих нулей, например, бит числа A с номером 12 должен быть записан как A12. Вокруг каждого применения штриха Шеффера должны стоять скобки (согласно третьему правилу). Внутри формулы не должно быть пробелов.
Входные данные
Вход содержит число N (1 ⩽ N ⩽ 100).
Выходные данные
Выведите формулу, вычисляющую бит переполнения суммы двух N-битных чисел A и B по правилам, описанным в условии. Для обозначения штриха Шеффера используйте символ | (ASCII код 124).
Размер выходного файла не должен превосходить 50N байт.
Примеры
Входные данные
2
Выходные данные
((((A0|B0)|(A0|B0))|((A1|A1)|(B1|B1)))|(A1|B1))