Перебор подмножеств

Пусть дано множество из \(n\) элементов. Будем рассматривать различные способы выбрать несколько элементов из данных (без учёта порядка), то есть все возможные подмножества данного множества. Тогда каждое подмножество удобно кодировать строкой из \(n\) символов, равных 0 или 1, где \(i\)-й символ будет обозначать, входит ли \(i\)-й элемент в выбранное подмножество. Указанные строки также можно интерпретировать, как двоичные числа от 0 до \(2^n-1\), и перебрать все подмножества можно при помощи цикла:

for (int mask = 0; mask < 1 << n; ++mask)
for mask in range(2 ** n):

а для определения, входит ли \(i\)-й элемент в данное подмножество удобно использовать битовые операции.

Упражнения

A: Вывести все подмножества (C++)

Дано число \(n\), выведите \(2^n\) строк из символов 0 и 1, соответствующих всем подмножествам данного множества в лексикографическом порядке.

Ввод	Вывод
2	00 01 10 11

B: Задача о рюкзаке (C++)

Грузоподъемность машины \(M\) килограмм. Есть \(n\) ящиков с грузами, масса \(i\)-го ящика равна \(m_i\). Определите, какую наибольшую массу грузов можно увезти на автомашине.

Программа получает на вход целое число \(M\), затем количество ящиков \(n\le 16\), затем \(n\) целых чисел от 1 до \(10^8\) в одной строке через пробел — массы ящиков.

Программа должна вывести единственное число — максимальную массу, которую можно увезти на машине.

Ввод	Вывод
10 4 1 3 5 8	9

С: Балансировка (Python)

\(n\) мест багажа нужно разложить по двум отсекам в самолёте так, чтобы сбалансировать нагрузку, то есть чтобы разница между суммарным весом багажа в отсеках была минимальна.

Первая строка входных данных содержит число \(n\le 16\), следующая строка содержит \(n\) целых чисел от 1 до \(10^8\) через пробел — веса мест багажа.

Программа должна вывести номера мест багажа (числа от 1 до \(n\)), которые нужно положить в один из отсеков для того, чтобы минимизировать разность массы багажа в двух отсеках.

Ввод	Вывод
5 28 17 31 14 26	1 3

D: Задача о покрытии множества (C++)

Премьер-министр некоторого государства хочет составить новый кабинет министров. К составу нового кабинета есть следующие требования.

Министров должно быть как можно меньше;
Для каждой области государственной деятельности (строительство, финансы, внешняя политика и т.д.) должен быть хотя бы один министр, который в ней разбирается.

На рассмотрение премьер-министра поступило \(n\) кандидатур. Определите, сколько и каких людей должны получить министерские посты.

Cначала вводится число \(n\) (натуральное, не превышает 15) — количество кандидатов в списке, затем вводится число \(k\) (натуральное, не превышает 20) — общее количество областей, в которых министры должны разбираться. Затем идет \(n\) строк следующего формата: в начале строки вводится числo \(p_i\) — (натуральное, не превышает \(k\)) — количество областей, в которых разбирается \(i\)-й кандидат, потом вводятся номера этих областей (натуральные числа, не превышают \(k\)).

Выведите номера министров, которых необходимо назначить.

Решение этой задачи будет приниматься, если множества компетенций каждого министра также храняться в виде битовой маски, для проверки того, что выбранное подмножество министров содержит все компетенции необходимо взять побитовую дизъюнкцию их масок.

Ввод	Вывод
3 2 2 1 2 2 1 2 2 1 2	1
4 3 1 1 1 2 1 3 2 1 2	3 4

E: Равенство (Python)

Дано выражение: \[a_1 ? a_2 ? ... ? a_n = S\]

Посчитайте, сколькими способами в этом выражении можно заменить вопросительные знаки на знаки операций сложения и умножения так, чтобы выполнялось равенство.

Программа получает на вход числа \(n\) (\(1\le n\le 16\)\) и \(S\), записанных в одной строке через пробел. Далее идет \(n\) натуральных чисел \(a_i\). Ограничения на \(S\) и \(a_i\) не даются, т.к. программа сдаётся на Python.

Выведите одно число — количество расстановок знаков сложения и умножения, дающих верное равенство.

Для вычисления значения арифметического выражения, записанного в строке, в Python можно использовать функцию eval.

Ввод	Вывод
2 4 2 2	2

F: Задача о клике (C++)

Есть \(n\) человек, некоторые из которых знакомы друг с другом. Выберите максимальную клику — множество людей, в котором все знакомы друг с другом.

Первая строка входных данных содержит количество людей \(n\) (\(1\le n\le 12\)). В следующих \(n\) строках задано отношение знакомства между ними в виде матрицы смежности: \(n\) строк по \(n\) чисел в каждой. Число, стоящее в \(i\)-й строке \(j\)-м столбце равно 1, если люди \(i\) и \(j\) знакомы и равно 0, если незнакомы.

Матрица симметрична относительно главной диагонали, на диагонали стоят нули.

Выведите номера людей, входящих в максимальную клику. Нумерация начинается с 1.

Решение этой задачи будет приниматься, если граф также храниться в виде битовых масок (для каждой вершины храним маску вершин, с которыми она соединена). Для проверки того, что выбранное подмножество является кликой, необходимо сделать побитовую конъюнкцию масок.

Ввод	Вывод
5 0 1 0 0 0 1 0 1 0 1 0 1 0 1 1 0 0 1 0 1 0 1 1 1 0	2 3 5

G: Теорема Рамсея (Python)

Теорема Рамсея гласит, что в любом достаточно большом полном графе, рёбра которого покрашены в два цвета, обязательно найдётся полный подграф из \(r\) вершин, покрашенный в первый цвет или полный подграф из \(s\) вершин, покрашенный во второй цвет. Величины \(R(r, s)\) — такие минимальные числа, что в любом полном графе с \(R(r, s)\) вершин найдётся полный подграф из \(r\) вершин цвета 1 или полный подграф из \(s\) вершин цвета 2, называются числами Рамсея.

Наиболее известен наименьший нетривиальный пример этой теоремы: в любой компании из 6 человек найдётся трое попарно знакомых или найдётся трое попарно незнакомых, так как \(R(3, 3)=6\).

По данному полному графу из \(n\) вершин, покрашенному в два цвета и данным числам \(r\) и \(s\) найдите в нём полный подграф из \(r\) вершин цвета 1 или полный подграф из \(s\) вершин цвета 2.

Первая строка входных данных содержит три числа \(n\), \(r\), \(s\) (\(r\ge 2\), \(s\ge 2\), \(R(s,r) \le n \le 18\)). В следующих \(n\) строках задана матрица смежности графа, число в \(i\)-й строке в \(j\)-м столбце равно 1 или 2 — цвет ребра, соединяющего вершины \(i\) и \(j\).

Матрица симметрична относительно главной диагонали, на диагонали стоят нули.

Если в данном графе есть полный подграф из \(r\) вершин цвета 1, то программа должна вывести число 1, а в следующей строке \(r\) чисел — номера вершин.

Если в данном графе есть полный подграф из \(s\) вершин цвета 2, то программа должна вывести число 2, а в следующей строке \(s\) чисел — номера вершин.

Ввод	Вывод
6 3 3 0 1 2 2 1 2 1 0 1 1 2 1 2 1 0 2 2 1 2 1 2 0 1 1 1 2 2 1 0 2 2 1 1 1 2 0	1 2 4 6

H: Минимальное контролирующее множество (C++)

В городе \(n\) площадей соединённых улицами. Каждая улица соединяет две какие-то площади.

Вам необходимо расставить минимальное число стражников на площадях так, чтобы для каждой улицы нашёлся стражник, стоящий на площади в одном из её концов. То есть стражники должны контролировать все улицы.

Первая строка входных данных содержит два числа \(n\) и \(m\) — количество площадей и количество улиц (\(1\le n\le 15\), \(1\le m \le 60\)). Следующие \(m\) строк содержат описание улиц, каждая строка содержит два различных числа от 1 до \(n\) — номера площадей, которые соединяет данная улица.

Программа должна вывести номера площадей, на которых необходимо поставить стражников.

Ввод	Вывод
5 6 1 3 2 3 2 5 3 5 3 4 4 5	3 5

I: Импликация и свёртка (Python)

Импликация — логическая функция \(x\Rightarrow y\), которая задаётся следующей таблицей истинности.

\(x\)	\(y\)	\(x\Rightarrow y\)
0	0	1
0	1	1
1	0	0
1	1	1

Теперь рассмотрим логическую функцию от \(n\) логических переменных, являющейся свёрткой импликации: \(f(x_1, x_2, ..., x_n) = \left(\left((x_1\Rightarrow x_2) \Rightarrow x_3\right) ... \right) \Rightarrow x_n\).

Постройте таблицу истинности данной функции. Программа получает на вход число \(n\ge 2\) и должна вывести \(2^n\) строк. В каждой строке записаны значения переменных \(x_1, x_2, ..., x_n\), а затем через пробел значение \(f(x_1, x_2, ..., x_n)\). Строки выводятся в лексикографическом порядке.

Ввод	Вывод
2	00 1 01 1 10 0 11 1
3	000 0 001 1 010 0 011 1 100 1 101 1 110 0 111 1

J: Задача из ЕГЭ-2013 (C++)

В ЕГЭ-2013 была такая задача. Решать её предполагалось аналитически, поэтому с переходом ЕГЭ в компьютерную форму такого рода задания потеряли смысл, но мы решим его при помощи компьютера.

Определите сколько существует различных наборов логических переменных \(x_1\), \(x_2\), ..., \(x_n\), которые удовлетворяют всем перечисленным ниже условиям. \[ \left\{ \begin{aligned} \overline{x_1\equiv x_2}&\wedge \left((x_1 \wedge \overline{x_3}) \vee (\overline{x_1} \wedge x_3)\right)&= 0,\\ \overline{x_2\equiv x_3}&\wedge \left((x_2 \wedge \overline{x_4}) \vee (\overline{x_2} \wedge x_4)\right)&= 0,\\ ...\\ \overline{x_{n-2}\equiv x_{n-1}}&\wedge \left((x_{n-2} \wedge \overline{x_n}) \vee (\overline{x_{n-2}} \wedge x_{n})\right)&= 0. \end{aligned} \right. \]

Здесь функция \(x\equiv y\) — это функция «эквивалентность», которая задаётся следующей таблицей истинности.

\(x\)	\(y\)	\(x\equiv y\)
0	0	1
0	1	0
1	0	0
1	1	1

Программа получает на вход число \(n\) (\(3\le n\le 16)\) и должна вывести количество решений указанной системы от \(n\) переменных.

Ввод	Вывод
10	20

K: Задача из ЕГЭ-2020 (Python)

А вот задача 23 из ЕГЭ-2020 долго будоражила умы. Приведём пример такой задачи. Рассмотрим \(n+m\) переменных \(x_1, x_2, ..., x_n, y_1, y_2, ..., y_m\). Рассмотрим \((n-1)(m-1)\) уравнeний вида: \[ \left((x_i\wedge y_j) \Rightarrow(x_i\wedge y_{j+1})\right) \wedge \left((x_i\wedge y_j) \Rightarrow(x_{i+1}\wedge y_j) \right) = 1 \]

где \(1\le i< n\), \(1\le j < m\).

Найдите количество наборов переменных, для которых верны все эти уравнения.

Программа получает на вход числа \(n\) и \(m\) (\(n\ge 2\), \(m\ge 2\), \(n+m\le 15\)) в отдельных строках и должна вывести одно число.

Ввод	Вывод
8 5	600

X: Эквивалентность логических формул (Python)

Две логические формулы называются эквивалентными, если на любом наборе переменных их значения равны. Вам даны две формулы, проверьте, эквивалентны ли они.

Первая строка входных данных содержит число \(n\), \(1\le n\le 6\). Следующие две строки содержат по одной логической формуле. Каждая формула может содержать переменные, обозначаемые x1, x2 и т.д., операции and, or и not и круглые скобки. Выражение является корректным выражением для языка Python.

Программа должна вывести YES, если формулы эквивалентны или NO в противном случае.

Указание. Воспользуйтесь функцией eval языка Python, аргумент которой строка, функция возвращает результат выражения, записанного в этой строке.

Ввод	Вывод
2 x1 and x2 not(not x1 or not x2)	YES
3 x1 and x2 and x3 x1 and x2 and not x3	NO

Y: Построить логическое выражение (Python)

Вам дана произвольная логическая функция от \(n\) переменных. Постройте логическое выражение, тождественное этой функции, используя только операции конъюнкции, дизъюнкции и отрицания.

Первая строка входных данных содержит число \(n\) (\(1\le n\le 6\)). Во второй строке заданы значения этой функции на \(2^n\) возможных значениях аргументов. \(i\)-й символ этой строки (в нумерации с нуля) равен значению функции на наборе \(x_1, ..., x_n\) таком, что двоичная запись числа \(\overline{x_1 ... x_n}_2=i\).

Программа должна вывести одну строку, содержащую некоторое корректное выражение на языке Python. Выражение может содержать переменные x1, x2 и т.д., операции and, or, not и круглые скобки. Выражение не обязательно должно быть кратчайшим, но оно не должно быть пустым, также длина выражения не должна превышать \(10^5\) символов.

Ввод	Вывод
2 0111	x1 or x2
2 1101	x2 or not x1
1 10	not x1

Во втором примере задана импликация \(x_1\Rightarrow x_2\).

Z: Ханаби (C++)

В популярной кооперативной карточной игре Ханаби игроки держат в руках карты, показывая их другим игрокам, но не себе, а задача игроков при помощи подсказок объяснить друг другу, какие карты они держат в руках.

Карты бывают 25 различных видов: 5 различных цветов (обозначим их Red, Green, Blue, Yellow, White) и 5 различных значений (от 1 до 5). Карт одного вида может быть несколько.

Подсказки же бывают такие: “вот эти карты зелёные” или “вот эти карты — тройки”, при этом указывается на все карты данного цвета или на все карты данного значения.

Пусть у Аграфены на руках в конце игры оказалось несколько карт, и она даже в точности знает значения этих карт. Но она не знает, в каком порядке они находятся, то есть её неизвестна перестановка этих карт. Какое минимальное число подсказок должны дать Аграфене её партнёры (они видят её карты и их расположение), чтобы Аграфена смогла определить значение каждой карты в её руке?

Программа получает на вход строку, в которой записаны значения карт на руках у Аграфены. Каждая карта описывается двумя символами: цветом (R, G, B, Y, W) и значением (1, 2, 3, 4, 5). Описания карт разделены пробелом, карты могут повторяться, всего у Аграфены не более 100 карт в руках.

Программа должна вывести единственное число: минимальное количество подсказок, которое необходимо Аграфене для определения всех её карт.

Ввод	Вывод	Пояснение
R2 R2	0	Без подсказок Аграфена знает, что каждая карта в её руке — это R2
W5 G5 G2 B2	2	Нужно дать подсказку по цвету G и по значению 5 (или по цвету G и по значению 2).
R2 G2 B2 Y2 W2	4	Все карты различаются только цветом, нужно дать 4 подскази про 4 любых цвета.