meet-in-the-middle Автоматизированная система генерации тестов

Твитнуть

Плюсануть

Класснуть

Запинить

Олимпиадный тренинг

Вы можете самостоятельно решать эти задачи столько раз, сколько вам это понадобится.


F. Xor-пути meet-in-the-middle битмаски дп Перебор *2100 Задано прямоугольное поле размера $n \times m$. В каждой клетке записано целое число; число, записанное в клетке ($i, j$) равно $a_{i, j}$. Ваша задача — посчитать количество путей из клетки ($1, 1$) в клетку ($n, m$), удовлетворяющих следующим условиям: Из клетки можно перемещаться только вниз или только вправо. Более формально, из клетки ($i, j$) можно переместиться в клетку ($i, j + 1$) или в клетку ($i + 1, j$). Клетка, в которую совершается перемещение, не может находиться за пределами поля. Xor всех чисел на пути из клетки ($1, 1$) в клетку ($n, m$) должен быть равен $k$ (xor это побитовое исключающее ИЛИ, эта операция представлена как '^' в Java или C++ и "xor" в Pascal). Найдите количество подходящих путей для заданного поля. Входные данные Первая строка входных данных содержит три целых числа $n$, $m$ и $k$ ($1 \le n, m \le 20$, $0 \le k \le 10^{18}$) — высота и ширина поля, и число $k$. Следующие $n$ строк содержат по $m$ целых чисел каждая, где $j$-й элемент $i$-й строки равен $a_{i, j}$ ($0 \le a_{i, j} \le 10^{18}$). Выходные данные Выведите одно целое число — количество путей из ($1, 1$) в ($n, m$) с xor всех чисел на пути равным $k$. Примечание Все пути из первого тестового примера: $(1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 2) \rightarrow (3, 3)$; $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3)$; $(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3)$. Все пути из второго тестового примера: $(1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 2) \rightarrow (3, 3) \rightarrow (3, 4)$; $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3) \rightarrow (3, 4)$; $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (2, 4) \rightarrow (3, 4)$; $(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3) \rightarrow (3, 4)$; $(1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3) \rightarrow (3, 4)$.
D. Загадочное преступление meet-in-the-middle Комбинаторика математика Перебор *1700 Ацингел — достаточно маленький городок. В этом городке был всего один доктор — Мисс Ада. Она была очень дружелюбной и никто никогда не говорил про неё ничего плохого. Так что кто мог подумать, что Аду найдут мёртвой в собственном доме? Мистер Гаври, известный во всём мире детектив, был назначен найти преступника. Он опросил $m$ соседей Ады о клиентах, которые посетили её в тот злосчастный день. Давайте пронумеруем этих клиентов от $1$ до $n$. Свидетельством каждого соседа является перестановка этих чисел, которая описывает порядок, в котором этот сосед видел клиентов приходящими к Аде. Однако некоторые факты выглядят достаточно подозрительно — как могло быть, что, согласно некоторым перестановкам некоторые клиенты были замечены утром, а согласно другим — вечером? «Утром некоторые из соседей скорее всего спали! — подумал Гаври, — А вечером слишком темно, чтобы видеть лица людей...». Теперь он хочет удалить из каждой перестановки некоторый префикс и некоторый суффикс (возможно, пустые) так, что оставшиеся части будут не пусты и равны друг другу. Возможно, часть потенциальных преступников пропадёт, но хотя бы не будет противоречий в свидетельствах соседей. Сколькими способами он может это сделать? Два способа называются разными, если в них отличается оставшаяся общая часть. Входные данные Первая строка содержит два целых числа $n$ и $m$ ($1 \le n \le 100\,000$, $1 \le m \le 10$) — количество подозреваемых и количество опрошенных соседей. Каждая из следующих $m$ строк содержит $n$ целых чисел $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$). Гарантируется, что эти числа образуют перестановку (то есть каждое число от $1$ до $n$ встречается ровно один раз). Выходные данные Выведите одно целое число — количество способов удалить из каждой перестановки некоторый префикс и суффикс (возможно, пустые) так, что оставшаяся часть была бы равной и непустой. Примечание В первом примере общей частью может быть $[1]$, $[2]$, $[3]$ и $[2, 3]$. Во втором и третьем примерах можно оставлять только общие части из $1$ элемента.
E. Помочь Хиасату meet-in-the-middle битмаски дп Перебор *2200 Хиасат недавно зарегистрировал новый аккаут на сайте NeckoForces и, как только его друзья об этом узнали, каждый из них захотел, чтобы его имя было названием хендла профиля Хиасата. К счастью для Хиасата, он может менять свой профиль в некоторые моменты времени. Также он знает моменты времени, когда его друзья будут заходить на его страницу. Формально, дана последовательность событий двух видов: $1$ — Хиасат может поменять свой хендл. $2$ $s$ — друг $s$ посещает профиль Хиасата. Друг $s$ будет счастлив, если каждый раз, когда он посетит страницу Хиасата, его хендл будет равен $s$. Хиасат просит вас помочь ему, выясните наибольшее количество счастливых друзей, которого можно добиться. Входные данные Первая строка содержит два целых числа $n$ и $m$ ($1 \le n \le 10^5, 1 \le m \le 40$) — количество событий и количество друзей. Затем следуют $n$ строк, задающих событие одно из двух видов: $1$ — Хиасат может поменять свой хендл. $2$ $s$ — друг $s$ ($1 \le \|s\| \le 40$) посещает профиль Хиасата. Гарантируется, что имя каждого друга состоит только из строчных латинских букв. Гарантируется, что первое событие обязательно первого типа, и что каждый друг посетит профиль Хиасата хотя бы один раз. Выходные данные Выведите одно целое число — наибольшее число счастливых друзей. Примечание В первом примере, оптимально поменять хендл на «motarack» в первом событие и на «light» в четвёртом. Таким образом, «motarack» и «light» будут счастливы, а «mike» — нет. Во втором примере можно выбрать «alice», «bob» или «tanyaromanova», и ровно этот друг и будет счастлив.
C. Кубворд *особая задача meet-in-the-middle дп Перебор Кубворд — особый вид кроссворда. Для построения кубворда сначала выбирается положительное целое число $a$ — длина стороны куба. Затем строится большой куб, состоящий из $a \times a \times a$ единичных кубиков. У большого куба 12 ребер. После этого выкидываются все единичные кубики, которые не касаются ребер большого куба. Рисунок ниже показывает, что получится при $a=6$. $\text{[math]}$ Наконец, вы пишете по одной букве в каждый единичный кубик. Вдоль каждого ребра большого куба должно получиться осмысленное слово. Буквы на любом ребре могут быть прочитаны в любом направлении, и достаточно, чтобы хотя бы в одном из направлений получилось осмысленное слово. Рисунок ниже показывает фигуру при $a=6$, где в некоторые единичные кубики уже записаны буквы. Уже можно прочитать слова «SUBMIT», «ACCEPT» и «TURING» вдоль трех ребер большого куба. $\text{[math]}$ Вам дан список осмысленных слов. Каждое слово из этого списка может сколько угодно раз читаться на ребрах кубворда. Найдите число различных кубвордов, которые можно составить из этих слов, по модулю $998,244,353$. Если один кубворд может быть получен из другого поворотом или отражением, они считаются различными. Входные данные Первая строка содержит одно целое число $n$ ($1 \leq n \leq 100,000$) – количество слов. Далее следуют $n$ строк. Каждая из этих строк содержит одно слово, которое может присутствовать на ребрах большого куба. Длина каждого слова находится в пределах от 3 до 10 включительно. Гарантируется, что все слова различны. Выходные данные Выведите одно целое число — количество различных кубвордов из данных слов по модулю $998,244,353$. Система оценки Подзадача 1 (21 балл): слова содержат только буквы «a» - «f» (строчные) Подзадача 2 (29 баллов): слова содержат только буквы «a» - «p» (строчные) Подзадача 3 (34 балла): слова содержат только буквы «a» - «p» (строчные) и «A» - «P» (заглавные) Подзадача 4 (16 баллов): слова содержат только буквы «a» - «z» (строчные), «A» - «Z» (заглавные) и цифры «0» - «9» Примечание В первом примере единственная возможность составить кубворд — написать слово «radar» на всех ребрах. Во втором примере есть два различных кубворда, которые получаются друг из друга поворотом: слово «robot» на всех ребрах, и разница лишь в том, содержит ли левый нижний передний угол букву «r» или «t». Третий пример похож на второй. То, что мы можем читать слова в обоих направлениях, не изменяет ответ. В четвертом примере есть один кубворд со словом «bob» на каждом ребре. Кроме того, есть $2^{12} = 4096$ кубов со словом «baobab» на каждом ребре: для каждого из 12 ребер есть два возможных направления, в которых можно написать слово «baobab».
G. Граф и числа meet-in-the-middle битмаски дп Комбинаторика Перебор *2900 Вам задан неориентированный граф из $n$ вершин и $m$ ребер. Вы должны написать число на каждой вершине графа, каждое число должно быть равно $0$ или $1$. После этого на каждом ребре будет записана сумма чисел на двух вершинах, инцидентных этому ребру. Вы должны выбрать числа таким образом, чтобы было хотя бы одно ребро с числом $0$, хотя бы одно ребро с числом $1$ и хотя бы одно ребро с числом $2$. Сколько способов так расставить числа? Два способа различны, если существует хотя бы одна вершина, на которой в разных способах записаны разные числа. Входные данные В первой строке заданы два целых числа $n$ и $m$ ($1 \le n \le 40$, $0 \le m \le \frac{n(n - 1)}{2}$) — количество вершин и ребер, соответственно. Затем следуют $m$ строк, в каждой из которых записаны два целых числа $x_i$ и $y_i$ ($1 \le x_i, y_i \le n$, $x_i \ne y_i$) — вершины, соединяемые $i$-м ребром. Гарантируется, что между каждой парой вершин существует не более одного ребра. Выходные данные Выведите одно целое число — количество способов так записать числа на вершинах, что есть хотя бы одно ребро с числом $0$, хотя бы одно ребро с числом $1$ и хотя бы одно ребро с числом $2$.
C2. Хорошие числа (сложная версия) meet-in-the-middle Бинарный поиск жадные алгоритмы математика *1500 Единственное отличие между простой и сложной версиями — максимальное значение $n$. Вам дано положительное целое число $n$. Вы очень любите хорошие числа, поэтому вам хочется найти минимальное хорошее число, большее или равное $n$. Положительное число называется хорошим, если оно может быть представлено в виде суммы различных степеней $3$ (т.е. повторения степеней $3$ запрещены). Например: $30$ — хорошее число: $30 = 3^3 + 3^1$, $1$ — хорошее число: $1 = 3^0$, $12$ — хорошее число: $12 = 3^2 + 3^1$, но $2$ не является хорошим числом: вы не можете представить его в виде суммы различных степеней $3$ ($2 = 3^0 + 3^0$), $19$ не является хорошим числом: вы не можете представить его в виде суммы различных степеней $3$ (например, представления $19 = 3^2 + 3^2 + 3^0 = 3^2 + 3^1 + 3^1 + 3^1 + 3^0$ не являются корректными), $20$ тоже не является хорошим числом: вы не можете представить его в виде суммы различных степеней $3$ (например, представление $20 = 3^2 + 3^2 + 3^0 + 3^0$ не является корректным). Обратите внимание, что существуют и другие представления $19$ и $20$ в качестве сумм степеней $3$, но ни одно из них не состоит из различных степеней $3$. Для заданного положительного числа $n$ найдите наименьшее $m$ ($n \le m$) такое, что $m$ — хорошее число. Вам необходимо ответить на $q$ независимых запросов. Входные данные Первая строка входных данных содержит одно целое число $q$ ($1 \le q \le 500$) — количество запросов. Затем следуют $q$ запросов. Единственная строка запроса содержит одно целое число $n$ ($1 \le n \le 10^{18}$). Выходные данные Для каждого запроса выведите наименьшее число $m$ (где $n \le m$) такое, что $m$ —хорошее число.
F. Сделай их похожими meet-in-the-middle битмаски Перебор хэши *2400 Назовем два числа похожими, если в их двоичных представлениях одинаковое количество цифр равно $1$. Например: $2$ и $4$ похожи (двоичные представления — $10$ и $100$); $1337$ и $4213$ похожи (двоичные представления — $10100111001$ и $1000001110101$); $3$ и $2$ не похожи (двоичные представления — $11$ и $10$); $42$ и $13$ похожи (двоичные представления — $101010$ и $1101$). Вам задан массив из $n$ целых чисел $a_1$, $a_2$, ..., $a_n$. Вы должны выбрать неотрицательное целое число $x$, после чего вы получите новый массив из $n$ чисел $b_1$, $b_2$, ..., $b_n$, где $b_i = a_i \oplus x$ ($\oplus$ обозначает операцию побитового исключающего ИЛИ). Можно ли получить такой массив $b$, в котором все числа похожи друг на друга? Входные данные В первой строке задано одно целое число $n$ ($2 \le n \le 100$). Во второй строке заданы $n$ целых чисел $a_1$, $a_2$, ..., $a_n$ ($0 \le a_i \le 2^{30} - 1$). Выходные данные Если нельзя выбрать такой $x$, что все элементы в полученном массиве будут похожи друг на друга, выведите $-1$. Иначе выведите любое неотрицательное целое число, не превосходящее $2^{30} - 1$, которое можно использовать как $x$ таким образом, что все числа в полученном массиве будут похожи друг на друга.
C. Вы все уже победители! meet-in-the-middle Бинарный поиск математика теория чисел *1400 На всеми известной тестирующей системе MathForces устраивается розыгрыш $n$ единиц рейтинга. Раздача рейтинга будет происходить по следующему алгоритму: если в мероприятии принимает участие $k$ участников, то $n$ рейтинга поровну распределяется между ними и округляется в сторону ближайшего меньшего целого числа. По окончании распределения может остаться неиспользованный рейтинг — он не достаётся никому из участников. К примеру, если $n = 5$ и $k = 3$, то каждый участник получит $1$ единицу рейтинга, а также $2$ единицы рейтинга останутся неиспользованными. Если же $n = 5$, а $k = 6$, то ни у кого из участников не увеличится рейтинг. Вася участвует в этом розыгрыше рейтинга, но не владеет информацией об общем количестве участников этого мероприятия. Поэтому он хочет узнать, какие различные значения приращения рейтинга он может получить в результате этого розыгрыша, и просит Вас о помощи. Например, если $n=5$, то искомый ответ равен последовательности $0, 1, 2, 5$. Каждое из значений последовательности (и только они) может быть получено как $\lfloor n/k \rfloor$ для некоторое подходящего целого положительного $k$ (где $\lfloor x \rfloor$ — округлённое вниз значение $x$): $0 = \lfloor 5/7 \rfloor$, $1 = \lfloor 5/5 \rfloor$, $2 = \lfloor 5/2 \rfloor$, $5 = \lfloor 5/1 \rfloor$. Напишите программу, которая по заданному $n$ находит последовательность всех возможных приращений рейтинга. Входные данные В первой строке входных данных записано целое число $t$ ($1 \le t \le 10$) — количество наборов входных данных в тесте. Далее следуют описания $t$ наборов входных данных, по одному описанию в строке. Каждая строка содержит целое число $n$ ($1 \le n \le 10^9$) — суммарное количество разыгрываемого рейтинга. Выходные данные Выведите ответы на $t$ заданных наборов входных данных. Каждый ответ должен состоять из двух строк. В первой строке выведите число $m$ — количество различных значений приращения рейтинга, которые может получить Вася. В следующей строке выведите $m$ различных чисел — сами значения приращения рейтинга в порядке возрастания.
H. Красно-синий граф meet-in-the-middle графы дп математика матрицы *3400 Дан ориентированный граф из $n$ вершин, пронумерованных от $1$ до $n$, в котором из каждой вершины (кроме $n$) исходит две дуги, красная и синяя. В любой момент времени ровно одна исходящая дуга является активной для каждой вершины. Изначально все синие дуги активны, а в вершине $1$ находится фишка. В начале каждой секунды у вершины, в которой стоит фишка, меняется активная дуга. Затем фишка перемещается по активной дуге. Когда фишка достигает вершины $n$, она останавливается. Гарантируется, что вершина $n$ достижима по дугам из всех остальных вершин графа. Вам задаются $q$ запросов, в каждом из которых описывается состояние графа — пара $(v, s)$ следующего вида: $v$ — вершина, в которой находится фишка; $s$ — строка из $n - 1$ символов. $i$-й символ обозначает, какая дуга, ведущая из $i$, активна (красная, если символ равен 'R', или синяя, если символ — 'B'). Для каждого запроса определите, достижимо ли заданное состояние из стартового, и если да — когда такое состояние графа появится в первый раз. Обратите внимание, что заданные две операции неразрывны между собой — состояние не считается достигнутым, если оно появляется после изменения активной дуги, но до того, как фишку переместили по дуге. Входные данные В первой строке задано одно целое число $n$ ($2 \leq n \leq 58$) — количество вершин. Далее следуют $n-1$ строк, $i$-я из которых содержит два целых числа $b_i$ и $r_i$ ($1 \leq b_i, r_i \leq n$), обозначающих синюю дугу $(i, b_i)$ и красную дугу $(i, r_i)$, соответственно. Гарантируется, что вершина $n$ достижима из всех остальных. Следующая строка содержит одно целое число $q$ ($1 \leq q \leq 5000$) — количество запросов. Затем следуют $q$ строк с запросами. $j$-я из них содержит целое число $v$ ($1 \leq v < n$) и строку $s$ из $n-1$ символов, каждый из которых либо 'R', либо 'B'. $i$-й из этих символов равен 'R', если красная дуга, ведущая из вершины $i$, активна, иначе этот символ равен 'B'. Выходные данные Выведите $q$ чисел, каждое из которых содержит ответ на один запрос. Если состояние в $i$-м запросе недостижимо, выведите $-1$. Иначе выведите $t_i$ — первый момент времени, когда это состояние появилось (выводите время в секундах, начиная отсчет с секунды $0$, в которую появилось стартовое состояние). Примечание На картине изображен граф из первого примера. $\text{[math]}$ Первые $19$ запросов показывают перемещение фишки. После $19$-го шага фишка достигает вершины $6$. Последние два запроса соответствуют недостижимым состояниям.
F1. Мудрецы (упрощенная версия) meet-in-the-middle битмаски дп Перебор *2600 Это упрощенная версия задачи. Две версии отличаются ограничением на число мудрецов и ограничением по времени. Вы можете взламывать по этой задаче только если обе версии решены. $n$ мудрецов живут в красивом городе. Некоторые из них знают друг друга. Для всех возможных $n!$ перестановок $p_1, p_2, \ldots, p_n$ мудрецов, построим бинарную строку длины $n-1$: для всех $1 \leq i < n$ положим $s_i=1$ если мудрецы $p_i$ и $p_{i+1}$ знают друг друга, и $s_i=0$ иначе. Для всех $2^{n-1}$ возможных бинарных строк, найдите число перестановок, при которых получается такая бинарная строка. Входные данные В первой строке записано одно целое число $n$ ($2 \leq n \leq 14)$ — количество мудрецов в городе. Следующие $n$ строк содержат бинарные строки, по $n$ символов в каждой, $j$-й символ в $i$-й строке равен «1» если мудрец $i$ знает мудреца $j$, и равен «0» иначе. Гарантируется, что если $i$-й мудрец знает $j$-го мудреца, то $j$-й мудрец знает $i$-го мудреца, и никакой мудрец не знает сам себя. Выходные данные Выведите $2^{n-1}$ целых чисел, разделенных пробелами. Для каждого $0 \leq x < 2^{n-1}$: Рассмотрим такую строку $s$ длины $n-1$, что $s_i = \lfloor \frac{x}{2^{i-1}} \rfloor \bmod 2$ для $1 \leq i \leq n - 1$. $(x+1)$-е число должно быть необходимому ответу для $s$. Примечание В первом тесте все мудрецы знакомы, соответственно для всех перестановок получается строка $11$. Во втором тесте Если $p = \{1, 2, 3, 4\}$, строка будет равна $101$, потому что мудрецы $1$ и $2$ знакомы, $2$ и $3$ не знакомы, $3$ и $4$ знакомы; Если $p = \{4, 1, 2, 3\}$, строка будет равна $110$, потому что мудрецы $1$ и $4$ не знакомы, $1$ и $2$ не знакомы, $2$ и $3$ не знакомы; Если $p = \{1, 3, 2, 4\}$, строка будет равна $000$, потому что мудрецы $1$ и $3$ не знакомы, $3$ и $2$ не знакомы, $2$ и $4$ не знакомы.
L. Light switches meet-in-the-middle *2600 Nikola owns a large warehouse which is illuminated by $N$ light bulbs, numbered $1$ to $N$. At the exit of the warehouse, there are $S$ light switches, numbered $1$ to $S$. Each switch swaps the on/off state for some light bulbs, so if a light bulb is off, flipping the switch turns it on, and if the light bulb is on, flipping the switch turns it off. At the end of the day, Nikola wants to turn all the lights off. To achieve this, he will flip some of the light switches at the exit of the warehouse, but since Nikola is lazy, he wants to flip the _minimum_ number of switches required to turn all the lights off. Since Nikola was not able to calculate the minimum number of switches, he asked you to help him. During a period of $D$ days, Nikola noted which light bulbs were off and which were on at the end of each day. He wants you to tell him the minimum number of switches he needed to flip to turn all the lights off for each of the $D$ days or tell him that it's impossible. Input First line contains three integers, $N$, $S$ and $D$ ($1 \leq N \leq 10^3$, $1 \leq S \leq 30$, $1 \leq D \leq 10^3$) – representing number of light bulbs, the number of light switches, and the number of days respectively. The next $S$ lines contain the description of each light switch as follows: The first number in the line, $C_i$ ($1 \leq C_i \leq N$), represents the number of light bulbs for which the on/off state is swapped by light switch $i$, the next $C_i$ numbers (sorted in increasing order) represent the indices of those light bulbs. The next $D$ lines contain the description of light bulbs for each day as follows: The first number in the line, $T_i$ ($1 \leq T_i \leq N$), represents the number of light bulbs which are on at the end of day $i$, the next $T_i$ numbers (sorted in increasing order) represent the indices of those light bulbs. Output Print $D$ lines, one for each day. In the $i^{th}$ line, print the minimum number of switches that need to be flipped on day $i$, or $-1$ if it's impossible to turn all the lights off.
F. Омкар и Акмар meet-in-the-middle бпф геометрия игры китайская теорема об остатках Комбинаторика Конструктив математика строковые суфф. структуры *2600 Омкар и Акмар играют в игру на круговой доске с $n$ ($2 \leq n \leq 10^6$) клетками. Клетки пронумерованы от $1$ до $n$, для каждой $i$ ($1 \leq i \leq n-1$) клетка $i$ соседствует с клеткой $i+1$, а клетка $1$ соседствует с клеткой $n$. Изначально каждая клетка пуста. Омкар и Акмар по очереди выкладывают на доску букву A или B, причем Акмар ходит первым. Буква должна быть помещена на пустую клетку. Кроме того, буква не может быть помещена в такую клетку, что соседняя клетка содержит ту же букву. Игрок проигрывает, когда наступает его очередь и больше нет допустимых ходов. Выведите количество возможных различных игр, в которых оба игрока играют оптимально по модулю $10^9+7$. Обратите внимание, что мы рассматриваем только те партии, в которых кто-то из игроков проиграл, и не осталось ни одного допустимого хода. Две игры считаются разными, если количества ходов в них отличаются, или на каком-то ходу буква или номер клетки, на которую ставится буква, были разными. Ход считается оптимальным, если он максимизирует шансы игрока на победу, предполагая, что другой игрок также играет оптимально. Более формально, если игрок, чья очередь ходить, имеет выигрышную стратегию, он должен сделать ход, после которого у него останется выигрышная стратегия. Если же у него ее нет, то он может сделать любой ход. Входные данные Первая строка будет содержать целое число $n$ ($2 \leq n \leq 10^6$) — количество клеток на доске. Выходные данные Выведите одно целое число, — количество возможных различных игр, в которых оба игрока играют оптимально по модулю $10^9+7$. Примечание В первом примере первый игрок имеет $4$ возможных хода. Независимо от того, как ходит первый игрок, у второго игрока есть ровно $1$ возможный ход, поэтому существует $4$ возможных игры.
E. Нижний уровень meet-in-the-middle Бинарный поиск графы жадные алгоритмы кратчайшие пути поиск в глубину и подобное *3000 В некоторой компьютерной игре игрок управляет героем, который характеризуется одним целочисленным параметром — силой. На текущем уровне герой попал в систему из $n$ пещер, пронумерованных от $1$ до $n$, и $m$ коридоров между ними. Каждый коридор соединяет две различные пещеры. Любые две пещеры соединены не более чем одним коридором. Из любой пещеры можно попасть в любую другую, двигаясь по коридорам. Герой начинает уровень в пещере $1$, а в каждой из оставшихся пещер находится монстр. Герой может перемещаться между пещерами по коридорам. Если герой вышел из пещеры и начал движение по коридору, он обязан завершить его и дойти до противоположного конца коридора. По любому коридору герой может перемещаться в обоих направлениях. Однако герой не может использовать один и тот же коридор два раза подряд. Формально, если герой перешёл по коридору из пещеры $i$ в пещеру $j$, он не может сразу же направиться обратно в пещеру $i$, но может направиться в любую другую пещеру, соединённую коридором с пещерой $j$. Известно, что из любой пещеры выходит как минимум два коридора, поэтому герой никогда не попадёт в тупик даже с учётом предыдущего требования. Чтобы пройти уровень, герою нужно победить монстров во всех пещерах. Когда герой впервые зайдёт в пещеру, ему придётся драться с монстром в ней. Герой может победить монстра в пещере $i$ только в том случае, если сила героя строго больше $a_i$. В случае победы над монстром сила героя увеличится на $b_i$. Если герой не может победить монстра, с которым он дерётся, игра заканчивается и игрок проигрывает. После того, как герой победит монстра в пещере $i$, все последующие визиты в пещеру $i$ не будут иметь последствий — монстра в этой пещере уже не будет, но и сила героя не будет изменяться. Найдите минимальную необходимую силу, с которой герой должен начать уровень, чтобы иметь возможность победить всех монстров и пройти уровень. Входные данные Во входных данных находятся несколько наборов входных данных. В первой строке задано одно целое число $t$ ($1 \le t \le 100$) — количество наборов входных данных. Первая строка набора входных данных содержит два целых числа $n$ и $m$ ($3 \le n \le 1000$; $n \le m \le min(\frac{n(n-1)}{2}, 2000)$) — число пещер и коридоров. Вторая строка содержит $n-1$ целых чисел $a_2, a_3, \ldots, a_n$ ($1 \le a_i \le 10^9$) — значения, с которыми сравнивается сила героя при битве с монстрами в пещерах $2, 3, \ldots, n$. Третья строка содержит $n-1$ целых чисел $b_2, b_3, \ldots, b_n$ ($1 \le b_i \le 10^9$) — прибавки к силе героя за победу над монстрами в пещерах $2, 3, \ldots, n$. Каждая из следующих $m$ строк содержит два целых числа $u_i$ и $v_i$ ($1 \le u_i, v_i \le n$; $u_i \ne v_i$) — номера пещер, соединённых коридором. Никакие две пещеры не соединены более чем одним коридором. Из любой пещеры можно попасть в любую другую, двигаясь по коридорам. Из любой пещеры выходит как минимум два коридора. Гарантируется, что сумма значений $n$ по всем наборам входных данных не превосходит $1000$, а сумма значений $m$ по всем наборам входных данных не превосходит $2000$. Выходные данные Для каждого набора входных данных выведите одно целое число — минимальную силу героя, необходимую для того, чтобы иметь возможность победить всех монстров и пройти уровень. Примечание В первом наборе входных данных герой может пройти уровень, начав с силы $15$, следующим образом: перейти из пещеры $1$ в пещеру $2$: так как $15 > 11$, герой побеждает монстра, сила героя увеличивается до $15 + 8 = 23$; перейти из пещеры $2$ в пещеру $3$: так как $23 > 22$, герой побеждает монстра, сила героя увеличивается до $23 + 7 = 30$; перейти из пещеры $3$ в пещеру $4$: так как $30 > 13$, герой побеждает монстра, сила героя увеличивается до $30 + 5 = 35$. Во втором наборе входных данных ситуация аналогична, но прибавки к силе героя в пещерах $2$ и $4$ поменялись местами. Герой может использовать другой маршрут, $1 \rightarrow 4 \rightarrow 3 \rightarrow 2$, и пройти уровень с начальной силой $15$. В третьем наборе входных данных герой может пройти уровень, начав с силы $19$, следующим образом: перейти из пещеры $1$ в пещеру $2$: так как $19 > 10$, герой побеждает монстра, сила героя увеличивается до $19 + 7 = 26$; перейти из пещеры $2$ в пещеру $4$: так как $26 > 20$, герой побеждает монстра, сила героя увеличивается до $26 + 10 = 36$; перейти из пещеры $4$ в пещеру $5$: так как $36 > 30$, герой побеждает монстра, сила героя увеличивается до $36 + 5 = 41$; перейти из пещеры $5$ в пещеру $2$: в этой пещере монстра уже нет, поэтому ничего не происходит; перейти из пещеры $2$ в пещеру $3$: так как $41 > 40$, герой побеждает монстра, сила героя увеличивается до $41 + 2 = 43$.
E. Восстановление турнирной таблицы meet-in-the-middle битмаски Перебор реализация хэши *2600 $2^k$ команд участвуют в плей-офф турнире. Турнир состоит из $2^k - 1$ игры. Они проводятся следующим образом: во-первых, команды делятся на пары: команда $1$ играет против команды $2$, команда $3$ играет против команды $4$ (именно в таком порядке) и так далее (таким образом, в этой фазе будет сыграно $2^{k-1}$ игры). Когда команда проигрывает игру, она выбывает, и каждая игра приводит к выбыванию одной команды (нет ничьих). После этого остается $2^{k-1}$ команд. Если остается только одна команда, она объявляется чемпионом; в противном случае играется еще $2^{k-2}$ игр: в первой из них победитель игры «$1$ против $2$» играет против победителя игры «$3$ против $4$», затем победитель игры «$5$ против $6$» играет против победителя игры «$7$ против $8$» и так далее. Этот процесс повторяется до тех пор, пока не останется только одна команда. Место команды в турнире зависит от того, в какой фазе турнира она выбыла: команда-победитель турнира занимает место $1$; команда, выбывшая в финале, занимает место $2$; обе команды, выбывшие в полуфинале, занимают место $3$; все команды, выбывшие в четвертьфинале, занимают место $5$; все команды, выбывшие в 1/8 финала, занимают место $9$, и так далее. Например, на этой картинке показан возможный ход турнира при $k = 3$, а также итоговые места команд при таком ходе турнира: $\text{[math]}$ После окончания турнира, который проходил по этим правилам, его результаты были закодированы следующим образом. Пусть $p_i$ — место, которое заняла $i$-я команда. Хэш турнира $h$ считается по формуле $h = (\sum \limits_{i=1}^{2^k} i \cdot A^{p_i}) \bmod 998244353$, где $A$ — некоторое заданное целое число. К сожалению, из-за сбоя системы почти вся информация о прошедшем турнире была утеряна. Остались только значения $k$, $A$ и $h$. Вам нужно по этим трем числам восстановить, какое место заняла какая команда (если это вообще возможно). Входные данные В единственной строке заданы три числа $k$, $A$ и $h$ ($1 \le k \le 5$; $100 \le A \le 10^8$; $0 \le h \le 998244352$). Выходные данные Если распределения команд по местам, удовлетворяющего всем требованиям, не существует, выведите $-1$. Иначе выведите $2^k$ чисел, $i$-е из которых должно быть равно $p_i$ (месту, занятому $i$-й командой). Обратите внимание: ваш ответ должен быть корректным вариантом результатов турнира, проводимого по описанным правилам; кроме того, структура турнира является фиксированной (например, команды $1$ и $2$ всегда играют между собой в первой фазе турнира). Если существует несколько способов восстановить места, занятые командами, выведите любой из них. Примечание Турнир из первого примера описан на картинке в условии. Для третьего примера, если выбрать расстановку команд по местам $[1, 2, 3, 3]$ (команда $1$ занимает место $1$, команда $2$ занимает место $2$, команды $3$ и $4$ занимают место $3$), можно получить хэш турнира, равный $7020100$ (при $A = 100$). Однако такое распределение мест не может быть результатом турнира, потому что команды $1$ и $2$ обязательно должны играть друг с другом в полуфинале, поэтому они не могут занять два первых места.
F. Красно-чёрное число meet-in-the-middle дп математика поиск в глубину и подобное реализация *2100 Дано целое неотрицательное число $x$, десятичная запись которого содержит $n$ цифр. Необходимо покрасить каждую его цифру в красный или чёрный цвет, так чтобы число, образуемое красными цифрами, делилось на $A$, а число, образуемое чёрными цифрами, делилось на $B$. Как в красный, так и в чёрный цвет должна быть покрашена хотя бы одна цифра. Из всех таких покрасок числа $x$, которые возможны, необходимо вывести любую такую, чтобы, если в красный покрашено $r$ цифр, а в чёрный — $b$ цифр, величина $\|r - b\|$ была минимально возможной. Обратите внимание, что число $x$, а также числа, образуемые цифрами одного цвета, могут содержать ведущие нули. $\text{[math]}$ Пример покраски числа для $A = 3$ и $B = 13$ На рисунке выше показан пример покраски числа $x = 02165$ из $n = 5$ цифр для $A = 3$ и $B = 13$. Красные цифры образуют число $015$, которое делится на $3$, а чёрные — $26$, которое делится на $13$. Заметим, что абсолютная величина разности количеств красных и чёрных цифр равна $1$, меньшего значения добиться невозможно. Входные данные В первой строке записано одно целое число $t$ ($1 \le t \le 10$) — количество наборов входных данных. Далее следуют $t$ наборов входных данных. Каждый набор входных данных состоит из двух строк. Первая строка содержит три целых числа $n$, $A$, $B$ ($2 \le n \le 40$, $1 \le A, B \le 40$). Вторая строка содержит целое неотрицательное число $x$, состоящее ровно из $n$ цифр и, возможно, содержащее ведущие нули. Выходные данные Для каждого набора входных данных выведите в отдельной строке: -1, если не существует искомой покраски; строку $s$ из $n$ символов, каждый из которых является буквой «R» или «B». Если $i$-я цифра числа $x$ красится в красный цвет, то $i$-й символ строки $s$ должен быть буквой «R», иначе буквой «B». Число, которое образовано покрашенными в красный цвет цифрами, должно делится на $A$. Число, которое образовано покрашенными в черный цвет цифрами, должно делится на $B$. Значение $\|r-b\|$ должно быть минимальным, где $r$ — количество красных цифр, а $b$ — количество чёрных. Если ответов несколько, то выведите любой из них. Примечание Первый набор входных данных разобран в условии. Во втором наборе входных данных нет чётных цифр, поэтому невозможно составить число, которое делится на $2$. В третьем наборе входных данных любая покраска, содержащая хотя бы одну красную и одну чёрную цифру, подходит, поэтому можно покрасить $4$ цифры в красный и $4$ в чёрный ($\|4 - 4\| = 0$, т. е. нельзя улучшить результат). В четвёртом наборе входных данных существует единственная искомая покраска.
F. Две сортировки meet-in-the-middle Бинарный поиск математика поиск в глубину и подобное *3400 Целые числа от $1$ до $n$ отсортировали по возрастанию в лексикографическом порядке, рассматривая их как строки, и получили массив $a_1, a_2, \dots, a_n$. Требуется найти сумму $(\sum_{i = 1}^n ((i - a_i) \mod 998244353)) \mod 10^9 + 7$. $x \mod y$ означает остаток от деления числа $x$ на число $y$ — этот остаток всегда неотрицателен и не превосходит $y - 1$, например $5 \mod 3 = 2$, $(-1) \mod 6 = 5$. Входные данные В первой строке содержится одно целое число $n$ ($1 \leq n \leq 10^{12}$). Выходные данные Выведите одно целое число — ответ на задачу. Примечание Строка $a$ лексикографически меньше строки $b$, если и только если выполняется один из следующих пунктов: $a$ — префикс $b$, но $a \ne b$; в первой позиции, где $a$ и $b$ различны, в строке $a$ находится буква, которая встречается в алфавите раньше, чем соответствующая буква в $b$. Например, $42$ меньше $6$ лексикографически, так как числа отличаются в первой позиции и $4 < 6$; $42 < 420$, так как $42$ является префиксом $420$. Обозначим $998244353$ за $M$. В первом примере последовательность $a$ будет равна $[1, 2, 3]$. $(1 - 1) \mod M = 0 \mod M = 0$ $(2 - 2) \mod M = 0 \mod M = 0$ $(3 - 3) \mod M = 0 \mod M = 0$ В результате $(0 + 0 + 0) \mod 10^9 + 7 = 0$ Во втором примере последовательность $a$ будет равна $[1, 10, 11, 12, 2, 3, 4, 5, 6, 7, 8, 9]$. $(1 - 1) \mod M = 0 \mod M = 0$ $(2 - 10) \mod M = (-8) \mod M = 998244345$ $(3 - 11) \mod M = (-8) \mod M = 998244345$ $(4 - 12) \mod M = (-8) \mod M = 998244345$ $(5 - 2) \mod M = 3 \mod M = 3$ $(6 - 3) \mod M = 3 \mod M = 3$ $(7 - 4) \mod M = 3 \mod M = 3$ $(8 - 5) \mod M = 3 \mod M = 3$ $(9 - 6) \mod M = 3 \mod M = 3$ $(10 - 7) \mod M = 3 \mod M = 3$ $(11 - 8) \mod M = 3 \mod M = 3$ $(12 - 9) \mod M = 3 \mod M = 3$ В результате $(0 + 998244345 + 998244345 + 998244345 + 3 + 3 + 3 + 3 + 3 + 3 + 3 + 3) \mod 10^9 + 7$ $=$ $2994733059 \mod 10^9 + 7$ $=$ $994733045$
F. Интересные отрезки meet-in-the-middle разделяй и властвуй Структуры данных *2800 $\text{[math]}$ У Василия есть массив неотрицательных чисел $a_1, a_2, \dots, a_n$. Он хочет, чтобы вы помогли ему узнать количество отрезков $l \le r$, которые проходят проверку. Проверка отрезка выполняется следующим образом: Находится минимум и максимум среди чисел на отрезке массива от $l$ до $r$. Проверка считается пройденной, если в битовой записи минимума и максимума одинаковое количество единичных бит. Входные данные Первая строка содержит одно число $n$ ($1 \le n \le 10^6$) — размер массива $a$. Вторая строка содержит $n$ целых чисел $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^{18}$) — описание массива $a$. Выходные данные Выведите одно число — количество отрезков, прошедших проверку.
G. Длинная бинарная строка meet-in-the-middle битмаски математика матрицы теория чисел *2900 У вас есть бинарная строка $t$ длины $10^{100}$, и изначально все биты в строке равны $\texttt{0}$. Вам также дана бинарная строка $s$, и вы можете выполнять следующую операцию: Выберите некоторую подстроку $t$ и замените ее на побитовое исключающее ИЛИ этой подстроки со строкой $s$.$^\dagger$ После некоторого количества операций в строке $t$ ровно два бита должны быть равны $\texttt{1}$; иными словами, должны существовать ровно два различных индекса $p$ и $q$ такие, что $p$-й и $q$-й биты строки $t$ равны $\texttt{1}$, а остальные биты равны $\texttt{0}$. Найдите лексикографически максимальную $^\ddagger$ строку $t$, которая может получиться при выполнении этого условия, или определите, что таких строк получиться не может. $^\dagger$ Формально, выберите индекс $i$ такой, что $0 \leq i \leq 10^{100}-\|s\|$. Для всех $1 \leq j \leq \|s\|$, если $s_j = \texttt{1}$, измените значение $t_{i+j}$. То есть если $t_{i+j}=\texttt{0}$, положите $t_{i+j}=\texttt{1}$. Иначе, если $t_{i+j}=\texttt{1}$, положите $t_{i+j}=\texttt{0}$. $^\ddagger$ Бинарная строка $a$ лексикографически больше бинарной строки $b$ такой же длины, если в первой позиции, где $a$ и $b$ различаются, строка $a$ содержит $\texttt{1}$, а строка $b$ — $\texttt{0}$. Входные данные Единственная строка содержит бинарную строку $s$ ($1 \leq \|s\| \leq 35$). Выходные данные Если нельзя получить подходящую под условие строку $t$, выведите -1. Иначе выведите два целых числа $p$ и $q$ ($1 \leq p < q \leq 10^{100}$) такие, что в лексикографически максимальной $t$ $p$-й и $q$-й биты равны $\texttt{1}$. Примечание В первом примере можно выполнить следующие операции. \texttt{00000}\ldots \to \color{red}{\texttt{1}}\texttt{0000}\ldots \to \texttt{1}\color{red}{\texttt{1}}\texttt{000}\ldots Во втором примере можно выполнить следующие операции. \texttt{00000}\ldots \to \color{red}{\texttt{001}}\texttt{00}\ldots \to \texttt{0}\color{red}{\texttt{011}}\texttt{0}\ldots В третьем примере можно выполнить следующие операции. \texttt{00000}\ldots \to \color{red}{\texttt{1111}}\texttt{0}\ldots \to \texttt{1}\color{red}{\texttt{0001}}\ldots Можно показать, что показанные выше строки $t$ лексикографически максимальны. В четвертом примере нельзя сделать ни один бит равным $\texttt{1}$, поэтому задача невыполнима.
F. Мультимножество строк meet-in-the-middle битмаски бпф графы Деревья дп математика Перебор Потоки *2500 Вам даны три целых числа $n$, $k$ и $f$. Рассмотрим все бинарные строки (то есть все строки, состоящие из символов $0$ и/или $1$) длины от $1$ до $n$. Для каждой такой строки $s$ вы должны выбрать целое число $c_s$ от $0$ до $k$. Мультимножество из бинарных строк длины ровно $n$ считается красивым, если для каждой бинарной строки $s$ длины от $1$ до $n$ выполняется следующее: количество строк в мультимножестве, для которых $s$ является префиксом, не превосходит $c_s$. Например, пусть $n = 2$, $c_{0} = 3$, $c_{00} = 1$, $c_{01} = 2$, $c_{1} = 1$, $c_{10} = 2$ и $c_{11} = 3$. Мультимножество строк $\{11, 01, 00, 01\}$ является красивым, так как: для строки $0$ существует $3$ строки из мультимножества, для которых $0$ — префикс, и $3 \le c_0$; для строки $00$ существует одна строка из мультимножества, для которой $00$ — префикс, и $1 \le c_{00}$; для строки $01$ существует $2$ строки из мультимножества, для которых $01$ — префикс, и $2 \le c_{01}$; для строки $1$ существует одна строка из мультимножества, для которой $1$ — префикс, и $1 \le c_1$; для строки $10$ существует $0$ строк из мультимножества, для которых $10$ — префикс, и $0 \le c_{10}$; для строки $11$ существует одна строка из мультимножества, для которой $11$ — префикс, и $1 \le c_{11}$. А теперь — сама задача. Вы должны посчитать количество способов выбрать числа $c_s$ для всех бинарных строк $s$ длины от $1$ до $n$ таким образом, чтобы максимальный возможный размер красивого мультимножества был равен ровно $f$. Входные данные В единственной строке заданы три целых числа $n$, $k$ и $f$ ($1 \le n \le 15$; $1 \le k, f \le 2 \cdot 10^5$). Выходные данные Выведите одно целое число — количество способов выбрать числа $c_s$ для всех бинарных строк $s$ длины от $1$ до $n$ таким образом, чтобы максимальный возможный размер красивого мультимножества был равен ровно $f$. Так как ответ может быть очень большим, выведите его по модулю $998244353$. Примечание В первом примере есть три способа выбрать значения $c_s$: $c_0 = 0$, $c_1 = 2$, тогда максимальное красивое мультимножество — $\{1, 1\}$; $c_0 = 1$, $c_1 = 1$, тогда максимальное красивое мультимножество — $\{0, 1\}$; $c_0 = 2$, $c_1 = 0$, тогда максимальное красивое мультимножество — $\{0, 0\}$.
E. Algebra Flash meet-in-the-middle битмаски графы Деревья дп математика Перебор *2500 Выпущена новая версия: Algebra Flash 2.2 Список изменений: Новый игровой режим! Благодарим вас за непрерывную поддержку игры! И это все? С небольшим разочарованием вы запускаете игру и нажимаете на новый режим. Написано «Цветные платформы». В ряд расположены $n$ платформ, пронумерованных от $1$ до $n$. В игре доступны $m$ цветов, пронумерованных от $1$ до $m$. $i$-я платформа раскрашена в цвет $c_i$. Вы начинаете на платформе $1$ и хотите добраться до платформы $n$. За один ход вы можете прыгнуть с некоторой платформы $i$ на платформы $i + 1$ или $i + 2$. Все платформы изначально деактивированы (включая платформы $1$ и $n$). Для каждого цвета $j$ можно заплатить $x_j$ монет, чтобы активировать все платформы этого цвета. Вы хотите включить некоторые платформы так, чтобы можно было начать на активированной платформе $1$, попрыгать по некотором активированным платформам и достичь платформы $n$. Какое наименьшее количество монет потребуется для достижения этого? Входные данные В первой строке записаны два целых числа $n$ и $m$ ($2 \le n \le 3 \cdot 10^5$; $1 \le m \le 40$) — количество платформ и количество цветов, соответственно. Во второй строке записаны $n$ целых чисел $c_1, c_2, \dots, c_n$ ($1 \le c_i \le m$) — цвета платформ. В третьей строке записаны $m$ целых чисел $x_1, x_2, \dots, x_m$ ($1 \le x_i \le 10^7$) — стоимости включения всех платформ каждого цвета. Выходные данные Выведите наименьшее количество монет, которое потребуется того, чтобы можно было начать на активированной платформе $1$, попрыгать по некотором активированным платформам и достичь платформы $n$.
H. Олимпийский тимбилдинг meet-in-the-middle Перебор *3500 Гвозден и Вукашин участвует в шахматной олимпиаде и хочет устроить тимбилдинг. Он собрал $n$ игроков, где $n$ является степенью $2$, и предложил заняться спортом. Гвозден и Вукашин входит в число этих $n$ человек. Одно из спортивных мероприятий — перетягивание каната. Для каждого $1\leq i \leq n$ сила $i$-го игрока равна $s_i$. Гвозден будет проводить раунды на выбывание до тех пор, пока не останется один игрок. Мы назовем этого игрока абсолютным победителем. В каждом раунде: Предположим, что $m>1$ игроков все еще в игре, где $m$ является степенью $2$. Эти $m$ игроков разбиваются на две команды равных размеров (т. е. по $m/2$ в каждой команде). Сила команды равна сумме сил всех игроков. Если команды имеют равные значения силы, то Гвозден выбирает, кто выигрывает; иначе выигрывает более сильная команда. Все игроки в проигравшей команде выбывают, и остается $m/2$ игроков. Гвозден может выбирать, как образуются команды на в каждом раунде, и команду-победителя в случае равных сил. Гвозден знает силу каждого игрока и ему интересно, кто может стать абсолютным победителем, а кто не может. Ответьте на этот вопрос. Входные данные Первая строка содержит одно целое число $n$ ($4 \leq n \leq 32$) — количество игроков. Гарантируется, что $n$ являются степенью $2$. Вторая строка содержит последовательность целых чисел $s_1,s_2, \ldots, s_n$ ($1 \leq s_i \leq 10^{15}$) — силы игроков. Выходные данные В единственной строке выведите бинарную строку $s$ длины $n$: $i$-й символ $s$ должен быть равен $1$, если $i$-й игрок может стать абсолютным победителем, и $0$ в противном случае. Примечание В первом примере игроки $1$ и $4$, имеющие силы $60$ и $87$, могут стать абсолютными победителями. Опишем процесс для игрока $1$. Изначально мы разделим игроков на команды $[1,3]$ и $[2,4]$. Силы команд равны $60+59=119$ и $32+87=119$. Так как они равны, то Гвозден может выбрать, кто выбывает, пусть это будет вторая команда. Остаются два игрока $1$ и $3$. Так как у $1$ сила больше ($60>59$), то он побеждает и становится абсолютным победителем. В третьем примере силы остающихся игроков может быть $[8,8,8,8,4,4,4,4] \rightarrow [8,8,4,4] \rightarrow [8,4] \rightarrow [8]$. Любой игрок с силой $8$ может стать абсолютным победителем, и можно показать, что все остальные не могут.
F. Даша и кошмары meet-in-the-middle битмаски Строки хэши *1900 Отличница Даша учится в лучшем математическом лицее страны. Недавно таинственный незнакомец принёс в лицей $n$ слов из маленьких латинских букв $s_1, s_2, \ldots, s_n$. С того дня Дашу начали мучить кошмары. Рассмотрим некоторую пару целых чисел $\langle i, j \rangle$ ($1 \le i \le j \le n$). Кошмаром называется строка, для которой верно: Она получена склеиванием $s_{i}s_{j}$; Её длина нечётна; Количество различных букв, входящих в неё, ровно $25$; Количество каждой отдельной буквы, входящей в неё, нечётно. Например, если $s_i=$ «abcdefg» и $s_j=$ «ijklmnopqrstuvwxyz», пара $\langle i, j \rangle$ образует кошмар. Даша знает, что кошмары исчезнут, если их посчитать. Кошмаров слишком много, поэтому Даше нужна ваша помощь. Посчитайте количество различных кошмаров. Кошмары считаются различными, если различны соответствующие им пары $\langle i, j \rangle$. Пары $\langle i_1, j_1 \rangle$ и $\langle i_2, j_2 \rangle$ считаются различными, если $i_1 \neq i_2$ или $j_1 \neq j_2$. Входные данные В первой строке дано единственное целое число $n$ ($1 \le n \le 2 \cdot 10^5$) — количество слов. В следующих $n$ строках записаны слова $s_1, s_2, \ldots, s_n$, состоящие из маленьких латинских букв. Гарантируется, что суммарная длина слов не превосходит $5 \cdot 10^6$. Выходные данные Выведите единственное целое число — количество различных кошмаров. Примечание В первом тесте кошмары образуются парами $\langle 1, 3 \rangle$, $\langle 2, 5 \rangle$, $\langle 3, 4 \rangle$, $\langle 6, 7 \rangle$, $\langle 9, 10 \rangle$.
F. Ещё одна n-мерная шоколадка meet-in-the-middle дп математика теория чисел *2700 Мама купила мальчику Васе $n$-мерную шоколадку, представляющую собой $n$-мерный куб, у которого длина каждой стороны равна $1$. У шоколадки намечено разделение на дольки. По $i$-му измерению ее можно разделить гиперплоскостями на $a_i$ равных частей. Таким образом, шоколадка делится суммарно на $a_1 \cdot a_2 \cdot a_3 \cdot \ldots \cdot a_n$ долек, у каждой дольки длина по $i$-му измерению равна $\frac{1}{a_i}$, соответственно объём каждой дольки равен $\frac{1}{a_1 a_2 \cdots a_n}$. Вася с друзьями хочет разрезать шоколадку, чтобы получилось хотя бы $k$ кусочков, при этом Вася хочет максимизировать объем наименьшего из них. Резать шоколадку можно только по местам соединения долек, причём каждый разрез должен проходить через всю шоколадку вдоль некоторой гиперплоскости, участвующей в образовании долек. Только сделав все разрезы, Вася разбирает шоколадку на кусочки. Более формально, Вася хочет выбрать числа $b_1, b_2, \dots, b_n$ ($1 \le b_i \le a_i$) — количество частей на которые Вася разрежет шоколадку вдоль каждого измерения. Должно выполняться условие $b_1 \cdot b_2 \cdot \ldots \cdot b_n \ge k$, чтобы получить не менее $k$ кусочков после всех разрезаний. Можно заметить, что при оптимальном разрезании с такими параметрами, минимальный кусочек будет содержать $\lfloor \frac{a_1}{b_1} \rfloor \dotsm \lfloor \frac{a_n}{b_n} \rfloor$ долек, а его объём будет равен $\lfloor \frac{a_1}{b_1} \rfloor \dotsm \lfloor \frac{a_n}{b_n} \rfloor \cdot \frac{1}{a_1 a_2 \cdots a_n}$. Вася хочет получить максимальное возможное значение объема минимального кусочка, умноженного на $k$, то есть он хочет максимизировать число $\lfloor \frac{a_1}{b_1} \rfloor \dotsm \lfloor \frac{a_n}{b_n} \rfloor \cdot \frac{1}{a_1 a_2 \cdots a_n} \cdot k$. Помогите ему в этом. Входные данные В первой строке даны два целых числа $n$ и $k$ $(1 \le n \le 100$, $1 \le k \le 10^7)$ — размерность шоколадки, и на сколько частей её нужно поделить. Во второй строке даны $n$ целых чисел $a_1,\ a_2,\ \dots,\ a_n$ $(1 \le a_i \le 10^7)$ — количество кусочков, на которое размечена шоколадка вдоль каждого из измерений. Выходные данные Выведите одно число — максимальный возможный объём наименьшего из полученных кусочков, умноженный на $k$, с абсолютной или относительной погрешностью не более $10^{-9}$. Если при заданных ограничениях разрезать шоколадку хотя бы на $k$ кусочков невозможно, выведите $0$. Примечание В первом примере одномерную шоколадку можно разделить так: $\text{[math]}$ Тогда ответ будет $\frac{2}{5} \cdot 2 = 0.8$ Во втором примере шоколадку можно разрезать следующим образом: $\text{[math]}$ Тогда ответ будет $\frac{2}{5} \cdot \frac{3}{10} \cdot 6 = 0.72$ В третьем примере шоколадку можно разрезать следующим образом: $\text{[math]}$ Тогда ответ будет $\frac{2}{4} \cdot \frac{1}{4} \cdot 7 = 0.875$
G1. В поисках истины (простая версия) meet-in-the-middle интерактив Конструктив математика Теория вероятностей *2200 Единственное отличие между версиями — максимальное количество запросов. В этой версии вы можете сделать не более $2023$ запросов. Это интерактивная задача. Вы играете в игру. Круг разделен на $n$ секторов, секторы пронумерованы от $1$ до $n$ в некотором порядке. Вы находитесь в соседней комнате и не знаете ни количество секторов, ни порядка их нумерации. Также есть стрелка, которая изначально указывает на какой-то сектор. Изначально ведущий сообщает вам номер сектора, на который указывает стрелка. После этого вы можете попросить ведущего переместить стрелку на $k$ секторов по часовой стрелке или против часовой стрелки не более чем $2023$ раза. И каждый раз вам сообщается номер сектора, на который указывает стрелка. Ваша задача определить число $n$ — количество секторов, используя не более чем $2023$ запроса. Гарантируется, что $1 \le n \le 10^6$. Входные данные Входные данные состоят из одного целого числа $x$ ($1 \le x \le n$) — номер начального сектора. Выходные данные После того, как вы определите число $n$ — количество секторов, выведите «! n» ($1 \le n \le 10^6$). После этого программа должна немедленно завершиться. Обратите внимание, что вывод ответа не считается запросом. Гарантируется, что число $n$ и номера секторов зафиксированы изначально и не будут меняться программой жюри в зависимости от запросов. Протокол взаимодействия После описания ввода вы можете задавать запросы. Запросы могут быть двух типов: «+ k» ($0 \le k \le 10^9$) — попросить переместить стрелку на $k$ секторов по часовой стрелке. «- k» ($0 \le k \le 10^9$) — попросить переместить стрелку на $k$ секторов против часовой стрелки. После каждого запроса вы должны считать целое число $x$ ($1 \le x \le n$) — номер текущего сектора, на который указывает стрелка. Всего вы можете сделать не более $2023$ запросов. Если вы сделаете слишком много запросов, вы получите вердикт Wrong answer. После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте: fflush(stdout) или cout.flush() в C++; System.out.flush() в Java; flush(output) в Pascal; stdout.flush() в Python; смотрите документацию для других языков. Примечание Взломы Для взломов используйте следующий формат теста. В первой строке выведите одно целое число $n$ ($1 \le n \le 10^6$) — количество секторов. Во второй строке выведите $n$ различных целых чисел $1 \le a_1, a_2, \dots, a_n \le n$ — номера секторов по часовой стрелке, стрелка изначально указывает на сектор с номером $a_1$.
G2. В поисках истины (сложная версия) meet-in-the-middle интерактив Конструктив математика Теория вероятностей *2500 Единственное отличие между версиями — максимальное количество запросов. В этой версии вы можете сделать не более $1000$ запросов. Это интерактивная задача. Вы играете в игру. Круг разделен на $n$ секторов, секторы пронумерованы от $1$ до $n$ в некотором порядке. Вы находитесь в соседней комнате и не знаете ни количество секторов, ни порядка их нумерации. Также есть стрелка, которая изначально указывает на какой-то сектор. Изначально ведущий сообщает вам номер сектора, на который указывает стрелка. После этого вы можете попросить ведущего переместить стрелку на $k$ секторов по часовой стрелке или против часовой стрелки не более чем $1000$ раз. И каждый раз вам сообщается номер сектора, на который указывает стрелка. Ваша задача определить число $n$ — количество секторов, используя не более чем $1000$ запросов. Гарантируется, что $1 \le n \le 10^6$. Входные данные Входные данные состоят из одного целого числа $x$ ($1 \le x \le n$) — номер начального сектора. Выходные данные После того, как вы определите число $n$ — количество секторов, выведите «! n» ($1 \le n \le 10^6$). После этого программа должна немедленно завершиться. Обратите внимание, что вывод ответа не считается запросом. Гарантируется, что число $n$ и номера секторов зафиксированы изначально и не будут меняться программой жюри в зависимости от запросов. Протокол взаимодействия После описания ввода вы можете задавать запросы. Запросы могут быть двух типов: «+ k» ($0 \le k \le 10^9$) — попросить переместить стрелку на $k$ секторов по часовой стрелке. «- k» ($0 \le k \le 10^9$) — попросить переместить стрелку на $k$ секторов против часовой стрелки. После каждого запроса вы должны считать целое число $x$ ($1 \le x \le n$) — номер текущего сектора, на который указывает стрелка. Всего вы можете сделать не более $1000$ запросов. Если вы сделаете слишком много запросов, вы получите вердикт Wrong answer. После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте: fflush(stdout) или cout.flush() в C++; System.out.flush() в Java; flush(output) в Pascal; stdout.flush() в Python; смотрите документацию для других языков. Примечание Взломы Для взломов используйте следующий формат теста. В первой строке выведите одно целое число $n$ ($1 \le n \le 10^6$) — количество секторов. Во второй строке выведите $n$ различных целых чисел $1 \le a_1, a_2, \dots, a_n \le n$ — номера секторов по часовой стрелке, стрелка изначально указывает на сектор с номером $a_1$.
I. Равные деревья особая задача meet-in-the-middle графы 3100 Задано два корневых дерева, состоящих из $n$ вершин каждое. Вершины в деревьях пронумерованы от $1$ до $n$, корень дерева — вершина $1$. Вы можете выполнять следующую операцию: выбрать дерево и вершину $v$ (кроме корня дерева) в нем; соединить дочерние узлы $v$ с родителем $v$ и удалить $v$ из дерева. Давайте скажем, что два дерева равны, если выполняются оба следующих условия: множества оставшихся вершин в обоих деревьях одинаковы; для каждой вершины $v$, которая не удалена, ее родитель в первом дереве такой же, как и ее родитель во втором дереве. Ваша задача — вычислить минимальное количество вышеупомянутых операций, чтобы сделать деревья равными. Входные данные Первая строка содержит одно целое число $n$ ($2 \le n \le 40$) — количество вершин в деревьях. Вторая строка содержит $n-1$ целых чисел $a_2, a_3, \dots, a_n$ ($1 \le a_i \le n$), где $a_i$ — родитель $i$-й вершины в первом дереве. Вершина $1$ — корень дерева. Третья строка содержит $n-1$ целых чисел $b_2, b_3, \dots, b_n$ ($1 \le b_i \le n$), где $b_i$ — родитель $i$-й вершины во втором дереве. Вершина $1$ — корень дерева. Выходные данные Выведите одно целое число — минимальное количество вышеупомянутых операций, чтобы сделать деревья равными.
E. Количество k-хороших подотрезков meet-in-the-middle битмаски дп Комбинаторика математика Перебор разделяй и властвуй *2300 Обозначим за $bit(x)$ количество единичных бит в двоичной записи неотрицательного целого числа $x$. Назовем подотрезок массива $k$-хорошим, если он состоит только из чисел, в которых не более $k$ единичных бит, то есть подотрезок $(l, r)$ массива $a$ хороший, если для любого $i$, такого, что $l \le i \le r$ выполняется $bit(a_{i}) \le k$. У вас есть массив $a$ длины $n$, состоящий из последовательных неотрицательных целых чисел начиная с $0$, то есть $a_{i} = i$ для $0 \le i \le n - 1$ (в $0$-индексации). Вам необходимо посчитать количество $k$-хороших подотрезков в этом массиве. Поскольку ответ может быть очень большим, выведите его по модулю $10^{9} + 7$. Входные данные Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит целое число $t$ ($1 \le t \le 10^{4}$) — количество наборов входных данных. Далее следует описание наборов входных данных. Единственная строка каждого набора входных данных содержит два целых числа $n$, $k$ ($1 \le n \le 10^{18}, 1 \le k \le 60$). Выходные данные Для каждого набора входных данных в отдельной строке выведите одно целое число — количество $k$-хороших подотрезков по модулю $10^{9} + 7$. Примечание Для первого набора входных данных $a = [0, 1, 2, 3, 4, 5]$, $k = 1$. Чтобы найти ответ, давайте запишем все числа в двоичной записи: a = [\color{green}{000}, \color{green}{001}, \color{green}{010}, \color{red}{011}, \color{green}{100}, \color{red}{101}] Отсюда видно, что числа $3$ и $5$ имеют $2 \ge (k = 1)$ единичных бита в двоичной записи, поэтому в ответ должны войти все подотрезки, в которых нет ни $3$, ни $5$, это отрезки (в $0$-индексации): ($0$, $0$), ($0$, $1$), ($0$, $2$), ($1$, $1$), ($1$, $2$), ($2$, $2$), ($4$, $4$).
G. Оптимизация решетки meet-in-the-middle битмаски Перебор хэши *3400 Рассмотрим граф на сетке, состоящей из $n$ строк и $n$ столбцов. Пусть ячейка в строке $x$ и столбце $y$ будет обозначена как $(x,y)$. Существует направленное ребро из $(x,y)$ в $(x+1,y)$ с неотрицательным целым значением $d_{x,y}$ для всех $1\le x < n, 1\le y \le n$, а также существует направленное ребро из $(x,y)$ в $(x,y+1)$ с неотрицательным целым значением $r_{x,y}$, для всех $1\le x \le n, 1\le y < n$. Изначально вы находитесь в точке $(1,1)$ с пустым множеством $S$. Вам нужно пройтись по ребрам и в конце концов достичь $(n,n)$. Каждый раз, когда вы проходите ребро, его значение будет добавляться в $S$. Найдите максимальный MEX$^{\text{∗}}$ множества $S$, который можно получить, достигнув точки $(n,n)$. $^{\text{∗}}$Минимальное исключенное число (MEX) массива — это наименьшее неотрицательное целое число, которое не принадлежит массиву. Например: MEX массива $[2,2,1]$ равен $0$, потому что $0$ не принадлежит массиву. MEX массива $[3,1,0,1]$ равен $2$, потому что $0$ и $1$ принадлежат массиву, а $2$ — нет. MEX массива $[0,3,1,2]$ равен $4$, потому что $0, 1, 2$ и $3$ принадлежат массиву, а $4$ — нет. Входные данные Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $t$ ($1\le t\le100$) — количество наборов входных данных. Далее следует описание наборов входных данных. Первая строка каждого набора входных данных содержит одно целое число $n$ ($2\le n\le20$) — количество строк и столбцов. Каждая из следующих $n-1$ строк содержит $n$ целых чисел, разделенных пробелами — матрица $d$ ($0\le d_{x,y}\le 2n-2$). Каждая из следующих $n$ строк содержит $n-1$ целых чисел, разделенных пробелами — матрица $r$ ($0\le r_{x,y}\le 2n-2$). Гарантируется, что сумма всех $n^3$ не превосходит $8000$. Выходные данные Для каждого набора входных данных выведите одно целое число — максимальное значение MEX для $S$ при достижении $(n,n)$. Примечание В первом наборе входных данных граф решетки и один из оптимальных путей выглядят следующим образом: $\text{[math]}$ Во втором наборе входных данных граф сетки и один из оптимальных путей выглядят следующим образом: $\text{[math]}$
D. Сумма перестановок meet-in-the-middle битмаски дп Комбинаторика реализация 1900 Перестановкой p называется упорядоченный набор чисел p₁, p₂, ..., p_n, состоящий из n различных целых положительных чисел, каждое из которых не больше чем n. Обозначим i-ый элемент перестановки p через p_i. Число n будем называть размером или длиной перестановки p₁, p₂, ..., p_n. Петя решил ввести операцию суммы на множестве перестановок длины n. Пусть заданы две перестановки длины n: a₁, a₂, ..., a_n и b₁, b₂, ..., b_n. Суммой перестановок a и b Петя назвал такую перестановку c длины n, у которой c_i = ((a_i - 1 + b_i - 1) mod* n) + 1 (1 ≤ i ≤ n). Операция $\text{[math]}$ обозначает взятие остатка от деления числа x на число y. Очевидно, что не для всех перестановок a и b будет существовать перестановка c, являющаяся их суммой. Из-за этого Петя расстроился и попросил Вас для заданного n посчитать количество таких пар перестановок a и b длины n, что существует перестановка c, являющаяся суммой a и b. Пара перестановок x, y (x ≠ y) и пара перестановок y, x считаются различными парами. Так как ответ может получиться достаточно большим, выведите его остаток от деления на 1000000007 (10⁹ + 7). Входные данные В единственной строке находится целое число n (1 ≤ n ≤ 16). Выходные данные В единственной строке выведите целое неотрицательное число — количество таких пар перестановок a и b, что существует перестановка c, которая является суммой a и b, по модулю 1000000007 (10⁹ + 7).
E. Идем по оси meet-in-the-middle битмаски дп Комбинаторика Конструктив *2300 Яхуб хочет встретиться со своей подружкой Яхубиной. Они оба живут на оси Ox (горизонтальной оси координат). Яхуб живет в точке 0, а Яхубина живет в точке d. У Яхуба есть n целых положительных чисел a₁, a₂, ..., a_n. Сумма этих чисел равняется d. Предположим, что p₁, p₂, ..., p_n — это перестановка чисел {1, 2, ..., n}. Затем, пусть b₁ = a_p₁, b₂ = a_p₂ и так далее. Будем называть массив b — «путь». Существует n! различных путей, один путь для каждой перестановки p. Яхуб запланировал поход к своей подружке следующим образом. Сначала он проходит b₁ шагов по оси Ox, затем делает привал в точке b₁. Затем он проходит еще b₂ шагов по оси Ox и устраивает привал в точке b₁ + b₂. Аналогично, в j-ый раз (1 ≤ j ≤ n) он проходит еще b_j шагов по оси Ox и делает привал в точке b₁ + b₂ + ... + b_j. Яхуб очень суеверный человек. У него есть k несчастливых целых чисел. Яхуб называет путь «хорошим», если он никогда не делает привала в точке, соответствующей хотя бы одному из этих k чисел. Просто из любопытства посчитайте, сколько существует хороших путей по модулю 1000000007 (10⁹ + 7). Входные данные В первой строке записано целое число n (1 ≤ n ≤ 24). В следующей строке записано n целых чисел: a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹). В третьей строке записано целое число k (0 ≤ k ≤ 2). В четвертой строке записано k положительных целых чисел, обозначающих несчастливые для Яхуба числа. Каждое из этих чисел не превышает 10⁹. Выходные данные Выведите единственное целое число — ответ на дилемму Яхуба. Примечание В первом тесте посмотрим на шесть возможных путей: [2, 3, 5]. Яхуб остановится в точках 2, 5 и 10. Среди них несчастливое число — 5. [2, 5, 3]. Яхуб остановится в точках 2, 7 и 10. Среди них несчастливое число — 7. [3, 2, 5]. Остановка в несчастливой точке 5. [3, 5, 2]. Такое расположение подходит. [5, 2, 3]. Два несчастливых привала (5 и 7). [5, 3, 2]. Яхуб не согласится, так как здесь есть привал в точке 5. Во втором тесте заметьте, что два разных способа могут иметь идентичные наборы привалов. В конкретном случае, все шесть возможных способов имеют одни и те же остановки: [2, 4, 6], так что тут неудача не грозит Яхубу.
D. Даты событий meet-in-the-middle жадные алгоритмы сортировки *1900 На уроке истории учитель попросил Васю назвать даты, когда произошли n известных событий. Он не помнит точные даты, но для каждого события он помнит отрезок дней [l_i, r_i] (включительно), в которые оно могло произойти. Однако еще Вася помнит, что в один день могло произойти только одно событие. Помогите ему выбрать такие n дат известных событий, чтобы оба условия выполнялись. Гарантируется, что решение существует. Входные данные В первой строке записано целое число n (1 ≤ n ≤ 100) — количество известных событий. Далее следует n строк по два целых числа l_i и r_i в каждой (1 ≤ l_i ≤ r_i ≤ 10⁷) — самая ранняя допустимая дата и самая поздняя допустимая дата i-го события. Выходные данные Выведите n чисел — даты, в которые произошли события. Если решений несколько, выведите любое. Гарантируется, что решение существует.
A. Золотая система счисления meet-in-the-middle математика *1700 Piegirl надоела двоичная, десятичная и все остальные системы счисления с целочисленным основанием. Недавно она обнаружила весьма интересные свойства числа $\text{[math]}$ , одно из из них можно записать следующим образом: q² = q + 1. Piegirl считает, что число q может быть неплохим основанием для новой системы счисления, которую она назовет «золотая система счисления». Число в золотой системе счисления — это непустая строка, состоящая из нулей и единиц. Десятичное значение числа a₀a₁...a_n равно $\text{[math]}$ . Немного поизучав новую систему счисления, Piegirl поняла, что эта система не обладает некоторыми свойствами, которыми обладают системы счисления с целочисленным основанием. В частности, сравнение двух чисел в этой системе счисления — не такая тривиальная задача. Вам заданы два числа в золотой системе счисления, сравните их. Входные данные Входные данные состоят из двух строк, в каждой из которых записана непустая строка из нулей и единиц. Длина каждой строки не превосходит 100000. Выходные данные Выведите «>», если первое число больше второго; выведите «<», если первое число меньше второго; иначе, выведите «=». Примечание В первом примере первое число равно $\text{[math]}$ , второе число приблизительно равно 1.618033988² + 1.618033988 + 1 ≈ 5.236. Очевидно, что первое число меньше. Во втором примере числа равны. Каждое из них приблизительно равно ≈ 2.618.
E. Перманент meet-in-the-middle дп математика Паросочетания *3100 Little X на днях решил #P полную задачу за полиномиальное время. Теперь он задает эту задачу вам! Дана особая матрица A размера n × n, ваша задача — подсчитать ее перманент по модулю 1000000007 (10⁹ + 7). Особое свойство матрицы A заключается в том, что почти все ее элементы равняются 1. Только k элементов имеют заданное значение. Определение перманента можно найти по следующей ссылке: https://ru.wikipedia.org/wiki/Перманент Входные данные В первой строке записано два целых числа через пробел, n, k (1 ≤ n ≤ 10⁵; 1 ≤ k ≤ 50). В следующих k строках записано описание матрицы. В i-й строке записано три целых числа через пробел x_i, y_i, w_i (1 ≤ x_i, y_i ≤ n; 0 ≤ w_i ≤ 10⁹). Эти числа обозначают, что A_{x_i, y_i} = w_i. Все элементы матрицы, кроме заданных, равны 1. Гарантируется, что все позиции (x_i, y_i) различны. Выходные данные Выведите перманент матрицы по модулю 1000000007 (10⁹ + 7).
E. Волнистые числа meet-in-the-middle Перебор поиск в глубину и подобное сортировки *2900 Волнистым числом называется такое целое положительное число, что для каждой цифры десятичного представления, не являющейся первой или последней, она либо строго больше обеих соседних с ней цифр, либо строго меньше обеих соседних с ней цифр. Например, числа 35270, 102, 747, 20 и 3 являются волнистыми, а числа 123, 1000 и 2212 — нет. Для двух заданных целых чисел n и k требуется найти k-е по величине волнистое число r, которое делится нацело на n. Ваша задача — написать программу для нахождения искомого числа r в случае, если оно не превосходит 10¹⁴. Входные данные В единственной строке содержатся два целых числа n и k, разделенных одним пробелом (1 ≤ n, k ≤ 10¹⁴). Выходные данные Требуется вывести единственное целое число r — ответ на задачу. Если такого числа не существует или оно больше 10¹⁴, то требуется вывести «-1» (минус единицу без кавычек). Примечание Значения первых четырех волнистых чисел кратных n для первого примера входных данных: 492, 615, 738 и 1845.
D. Шоколадки meet-in-the-middle математика Перебор поиск в глубину и подобное теория чисел *1900 Поликарпу нравится делать подарки Прасковье. Вот и сейчас он купил две плитки шоколада, каждая из них имеет форму прямоугольника из долек. Первая плитка имеет размеры a₁ × b₁ долек, а вторая — a₂ × b₂ долек. Поликарп хочет угостить на большой перемене Прасковью одной плиткой, а вторую съесть сам. Кроме того, он хочет подчеркнуть одинаковую значимость ума Поликарпа и красоты Прасковьи, поэтому плитки должны содержать одинаковое количество долек. Чтобы сделать плитки равными по количеству долек, Поликарп каждую минуту съедает немного шоколада. Каждую минуту он: либо разламывает одну плитку ровно пополам (вертикально или горизонтально) и съедает ровно половину шоколадки, либо отламывает от плитки ровно одну треть (вертикально или горизонтально) и съедает ровно треть шоколадки. В первом случае от плитки останется половина, а во втором — две трети. Не всегда возможны оба развития событий, а иногда бывает, что Поликарп вообще не может отломить половину или треть. Например, если плитка имеет размер 16 × 23, то от нее можно отломить половину, но нельзя одну треть. Если плитка имеет размер 20 × 18, то от нее можно отломить как половину, так и треть. Если плитка имеет размер 5 × 7, то отломить как половину так и треть невозможно. Какое минимальное количество минут понадобится Поликарпу, чтобы сделать обе плитки одинаковыми по количеству долек в них? Найдите не только искомое минимальное количество минут, но и возможные размеры плиток после их вынужденного «уравнивания». Входные данные В первой строке входных данных записаны целые числа a₁, b₁ (1 ≤ a₁, b₁ ≤ 10⁹) — первоначальные размеры первой шоколадки. Во второй строке входных данных записаны целые числа a₂, b₂ (1 ≤ a₂, b₂ ≤ 10⁹) — первоначальные размеры второй шоколадки. Вы можете использовать типы данных int64 (в Паскале), long long (в С++), long (в Java) для работы с большими целыми числами (превосходящими 2³¹ - 1). Выходные данные В первую строку выведите m — искомое минимальное количество минут. Во вторую и третью строки выведите возможные размеры плиток после их уравнивания за m минут. Выводите размеры, используя формат, аналогичный формату входных данных. Размеры (числа в выводимых парах) выводите в любом порядке. Вторая строка должна соответствовать первой шоколадке, а третья — второй. Если решений несколько, выведите любое из них. Если решения не существует, то выведите единственную строку с числом -1.
G1. Инверсии meet-in-the-middle дп Перебор поиск в глубину и подобное *1800 Вам дана перестановка из n чисел p₁, p₂, ..., p_n. Мы совершаем k операций следующего типа: выбираем равновероятно случайным образом два индекса l и r (l ≤ r) и меняем порядок элементов p_l, p_l + 1, ..., p_r на обратный. Ваша задача — определить математическое ожидание количества инверсий в итоговой перестановке. Входные данные Первая строка входных данных содержит два целых числа n и k (1 ≤ n ≤ 100, 1 ≤ k ≤ 10⁹). Следующая строка содержит n целых чисел p₁, p₂, ..., p_n — данную перестановку. Все p_i различны и находятся в интервале от 1 до n. Задача состоит из трех подзадач, которые отличаются друг от друга ограничениями на входные данные. За решение каждой подзадачи вы получите определенное количество баллов. Описание подзадач следует ниже. В подзадаче G1 (3 балла) выполняется 1 ≤ n ≤ 6, 1 ≤ k ≤ 4. В подзадаче G2 (5 баллов) выполняется 1 ≤ n ≤ 30, 1 ≤ k ≤ 200. В подзадаче G3 (16 баллов) выполняется 1 ≤ n ≤ 100, 1 ≤ k ≤ 10⁹. Выходные данные Выведите ответ на задачу с абсолютной или относительной погрешностью не более чем 1e - 9. Примечание Рассмотрим первый пример. В перестановке (1, 2, 3) (которая изначально не содержит инверсий) будет выбран один интервал и порядок его элементов будет изменен на обратный. С вероятностью $\text{[math]}$ , интервал будет состоять из одного элемента и перестановка не изменится. С вероятностью $\text{[math]}$ мы поменяем местами первые два элемента и получим перестановку (2, 1, 3) с одной инверсией. С такой же вероятностью мы можем выбрать интервал, состоящий из последних двух элементов, что приведет к перестановке (1, 3, 2), в которой тоже одна инверсия. Наконец, с вероятностью $\text{[math]}$ выбранный случайным образом интервал будет содержать все элементы, что приведет к перестановке (3, 2, 1) с тремя инверсиями. Таким образом, мат.ожидание количества инверсий равно $\text{[math]}$ .
B. Drazil и его счастливые друзья meet-in-the-middle Перебор снм теория чисел *1300 У Drazil много друзей. Некоторые из них счастливы, а некоторые несчастны. Drazil хочет, чтобы все его друзья были счастливы. Поэтому он придумал такой план. Среди его друзей n юношей и m девушек. Пронумеруем их от 0 до n - 1 и 0 до m - 1 соответственно. В i-й день Drazil приглашает $\text{[math]}$ -го юношу и $\text{[math]}$ -ю девушку поужинать (Drazil программист, поэтому i принимает значения с нуля). Если один из этих двух людей счастлив, то и другой становится счастливым. В противном случае оба человека останутся в том состоянии, в котором они были изначально. Как только человек становится счастливым (или же если он был счастлив с самого начала), он остается счастливым навсегда. Drazil интересно, приведёт ли этот план к тому, что его друзья рано или поздно все станут счастливыми. Помогите ему найти ответ на этот вопрос. Входные данные В первой строке следуют два целых числа n и m (1 ≤ n, m ≤ 100). Во второй строке следует целое число b (0 ≤ b ≤ n), — количество счастливых парней среди друзей Drazil, затем следуют b различных целых чисел x₁, x₂, ..., x_b (0 ≤ x_i < n), — номера счастливых парней. В третьей строке следует целое число g (0 ≤ g ≤ m), — количество счастливых девушек среди друзей Drazil, затем следуют g различных целых чисел y₁, y₂, ... , y_g (0 ≤ y_j < m), — номера счастливых девушек. Гарантируется, что у Drazil есть не менее одного несчастного друга. Выходные данные Если Drazil может осчастливить всех своих друзей, воспользовавшись этим планом, выведите "Yes". В противном случае выведите "No". Примечание Определим $\text{[math]}$ как остаток от целочисленного деления i на k. В первом тесте из условия: В 0-й день Drazil приглашает 0-го парня и 0-ю девушку. Так как 0-я девушка изначально счастливая, 0-й юноша становится счастлив в этот день. В 1-й день Drazil приглашает 1-го парня и 1-ю девушку. Они оба несчастны, так что в этот день ничего не меняется. Во 2-й день Drazil приглашает 0-го парня и 2-ю девушку. Так как 0-й парень уже счастлив, в этот день он делает 2-ю девушку счастливой. В 3-й день Drazil приглашает 1-го парня и 0-ю девушку. 0-я девушка счастливая, она делает счастливым 1-го парня. В 4-й день Drazil приглашает 0-го парня и 1-ю девушку. 0-ой парень счастлив, так что он делает 1-ю девушку счастливой. Итак, в этот момент все друзья Drazil становятся счастливыми.
E. Аня и кубики meet-in-the-middle Бинарный поиск битмаски дп математика Перебор *2100 Аня очень любит складывать и наклеивать. Сегодня она решила заняться именно этим. У Ани есть n кубиков, лежащих в ряд и пронумерованных от 1 до n слева направо, с написанными на них натуральными числами. Также у нее есть k наклеек с восклицательными знаками. Известно, что количество наклеек не превышает количества кубиков. Аня может наклеить на кубик восклицательный знак и получить факториал числа, записанного на кубике. Например, если на кубике было написано 5, то после наклеивания будет 5!, что равно 120. Вам нужно помочь Ане посчитать, сколько существует способов оставить какое-то количество кубиков и наклеить на некоторые из них восклицательные знаки, использовав не более k восклицательных знаков, так, чтобы сумма чисел, написанных на кубиках (как отмеченных восклицательными знаками, так и нет), после наклеивания стала равна S. Аня может наклеить на один кубик не более одного восклицательного знака. Справитесь? Два способа будем считать одинаковыми, если совпадают номера оставленных кубиков, а также совпадают номера кубиков, на которые наклеены восклицательные знаки. Входные данные В первой строке входных данных заданы через пробел три целых числа n, k и S (1 ≤ n ≤ 25, 0 ≤ k ≤ n, 1 ≤ S ≤ 10¹⁶) — количество кубиков и количество наклеек, которые есть у Ани, и сумма, которую необходимо набрать. Во второй строке следуют n целых положительных чисел a_i (1 ≤ a_i ≤ 10⁹) — числа, записанные на кубиках. На разных кубиках могут быть написаны одинаковые числа. Выходные данные Выведите в первую строку выходных данных единственное целое неотрицательное число — количество способов оставить какое-то количество кубиков и наклеить на некоторые из них восклицательные знаки так, чтобы сумма чисел стала равна заданному числу S. Примечание В первом тесте из условия единственный способ достичь желаемого — оставить оба кубика, и наклеить на каждый из них по восклицательному знаку. Во втором тесте из условия единственный способ достичь желаемого — оставить оба кубика, но не клеить восклицательный знак ни на один из них. В третьем тесте из условия можно оставить любой из трёх кубиков, при этом на него можно как клеить, так и не клеить восклицательный знак, поэтому существует шесть способов достичь желаемого.
F. Упрощенный японский кроссворд meet-in-the-middle битмаски дп хэши 2400 В этой задаче вам предстоит написать программу, решающую упрощенный японский кроссворд для полей не более 5 × 20. Упрощенный японский кроссворд — это головоломка, в которой надо построить такое поле (каждая клетка либо белая, либо черная), которое соответствует заданной информации для строк и столбцов. Для каждой строки и каждого столбца задано количество блоков из черных клеток. Ваша задача — построить такое поле, для которого все эти количества имеют место быть. Например, если размеры поля n = 3, m = 5, а количества блоков для строк это [2, 3, 2], а для столбцов — [1, 0, 1, 2, 1], то решение может выглядеть так: $\text{[math]}$ Гарантируется, что для каждого теста, на котором будет запущена ваша программа, хотя бы одно решение головоломки существует. Входные данные В первой строке входных данных записаны два целых числа n, m (1 ≤ n ≤ 5, 1 ≤ m ≤ 20) — количество строк и столбцов соответственно. Вторая строка содержит n целых чисел a₁, a₂, ..., a_n, где a_i — количество черных блоков в i-й строке искомого поля. Аналогично, третья строка содержит m целых чисел b₁, b₂, ..., b_m, где b_i — количество черных блоков в i-м столбце искомого поля. Гарантируется, что хотя бы одно решение головоломки существует. Выходные данные Выведите любое из возможных решений. Ваш вывод должен содержать n строк по m символов в каждой из них. Белую ячейку следует обозначать символом «.», а черную — символом «».
C. Ваня и весы meet-in-the-middle дп жадные алгоритмы математика Перебор теория чисел *1900 У Вани есть чашечные весы и гири массами w⁰, w¹, w², ..., w¹⁰⁰ грамм, где w — некоторое целое число не меньше 2 (ровно по одной гире каждого номинала). Ваня хочет узнать, может ли он взвесить вещь с массой m с помощью данных гирь, если гири можно класть на обе чаши весов. Формально говоря, требуется определить, можно ли положить вещь массой m и некоторые гири на левую чашу весов, а некоторые гири на правую чашу весов таким образом, чтобы чаши весов были уравновешены. Входные данные В первой строке содержатся два целых числа w, m (2 ≤ w ≤ 10⁹, 1 ≤ m ≤ 10⁹) — число, задающее массы гирь и массу вещи. Выходные данные Выведите слово 'YES', если вещь можно взвесить и 'NO', если нельзя. Примечание Пояснение к первому тесту из условия. На одной чаше может быть вещь массой 7 и гиря массой 3, а на второй чаше две гири массами 9 и 1 соответственно. Тогда 7 + 3 = 9 + 1. Пояснение ко второму тесту из условия. На одной чаше может быть вещь массой 99 и гиря массой 1, а на второй гиря массой 100. Пояснение к третьему тесту из условия. Взвесить вещь, как описано в условии, невозможно.
D. Lizard Era: Beginning meet-in-the-middle *2300 В игре Lizard Era: Beginning главному герою предстоит путешествие с тремя спутницами: Линн, Мелианой и Ворриган. Всего в игре n обязательных заданий, для выполнения каждого из них нужно взять ровно двух спутниц. Отношение каждой из спутниц к герою характеризуется целым числом. Изначально отношение каждой из них к герою нейтрально и равно 0. В процессе выполнения задания главный герой совершает поступки, которые изменяют отношение к нему спутниц, которых он взял на выполнение этого задания, в положительную или отрицательную сторону (а могут и не менять вовсе). Сообщите, каких спутниц нужно выбирать главному герою, чтобы после выполнения всех заданий значения их отношения к герою были равны между собой. Если это можно сделать несколькими способами, выберите тот, в котором эти значения наибольшие. Входные данные В первой строке содержится целое положительное число n (1 ≤ n ≤ 25) — количество заданий, обязательных для выполнения. Следующие n строк содержат описание заданий — i-я строка содержит три числа l_i, m_i, w_i — величины, на которые изменятся отношения к главному герою Линн, Мелианы или Ворриган соответственно, в случае, если герой возьмет их с собой на выполнение i-го задания. Все числа во входных данных целые и не превышают по абсолютному значению 10⁷. Выходные данные В случае, если решения не существует, в первой строке выведите "Impossible". В противном случае выведите n строк, в каждой из них по два символа — в i-й строке выводите первые буквы имен спутниц, которых герой должен взять с собой на выполнение i-ого задания ('L' — Линн, 'M' — Мелиана, 'W' — Ворриган). Буквы выводите в любом порядке. Если решений несколько, выведите любое.
F. Медведи и сок meet-in-the-middle дп математика *2900 В гостинице поселились n медведей, но там есть только p спальных мест. Медведи планируют закатить большую вечеринку на несколько ночей (и дней). Медведи любят пить сок. Они не любят вино, но не могут отличить его от сока ни по вкусу, ни по запаху. Медведь ложится спать, только если он выпил вина, при этом он уходит спать через несколько часов после этого. Он проснётся только спустя много дней, когда вечеринка уже будет окончена. Хозяин гостиницы Радевуш хочет предложить медведям несколько бочек с напитками. При этом ровно одна бочка будет содержать вино, а в остальных будет содержаться сок. После этого Радевуш предложит медведям определить, в какой бочке находится вино. Каждую ночь происходит следующее (ровно в таком порядке): Каждый медведь выбирает какой-то (возможно, пустой) набор бочек. Одна и та же бочка может быть выбрана несколькими медведями. Каждый медведь выпивает по одному стакану из каждой бочки, которую он выбрал. Все медведи, пившие вино, отправляются спать (то есть те медведи, у которых в множестве выбранных бочек была бочка с вином). Они просыпаются спустя много дней, когда вся вечеринка уже окончена. Если свободных спальных мест недостаточно, то медведи автоматически проигрывают. В конце вечеринки, если однозначно можно определить, в какой бочке находится вино, и хотя бы один медведь не спит, то медведи выигрывают (если, конечно, они не проиграли раньше, потому что кому-то не хватило спальных мест). Радевуш хотел бы, чтобы медведи выиграли. Он рассматривает q сценариев игры. В i-м сценарии вечеринка продолжается i ночей. Далее пусть R_i обозначает максимальное количество бочек, для которого медведи точно смогут выиграть, если будут действовать оптимально. Обозначим $\text{[math]}$ . Вам требуется вычислить $\text{[math]}$ , где $\text{[math]}$ означает побитовое исключающее или (также известное как XOR). Обратите внимание, что одна и та же бочка может быть выбрана несколькими медведями и все они одновременно пойдут спать, если она содержит вино. Входные данные В единственной строке входных данных записаны три целых числа n, p и q (1 ≤ n ≤ 10⁹, 1 ≤ p ≤ 130, 1 ≤ q ≤ 2 000 000) — количество медведей, количество спальных мест и количество сценариев соответственно. Выходные данные Выведите единственное целое число, равное $\text{[math]}$ . Примечание В первом примере в гостинице находятся 5 медведей и есть только 1 спальное место. Имеем R₁ = 6, R₂ = 11, R₃ = 16, так что ответ равен $\text{[math]}$ . Проанализируем стратегию для сценария с 2 днями. Всего есть R₂ = 11 бочек, и 10 из них содержат сок. В первую ночь i-й медведь выбирает бочку i. Если одна из 5 бочек содержит вино, то соответствующий медведь отправится спать. Таким образом, медведи выигрывают, потому они теперь знают где находится вино и есть хотя бы один не спящий медведь. Если никто из 5 медведей не ушёл спать, то на вторую ночь i-й медведь пьёт из бочки 5 + i. Если хотя бы одна из бочек 6 – 10 содержит вино, то соответствующий медведь отправится спать, и медведи победят. Если никто из медведей опять не уйдёт спать, то они точно будут знать, что вино находится в бочке 11. Во втором примере есть только один медведь. Он не может ничего пить (то есть он выбирает пустое множество бочек каждую ночь), потому что если он уйдёт спать, то медведи сразу проигрывают. Таким образом, для любого числа дней R_i = 1 и ответ равен $\text{[math]}$ .
G. МАТЕМАТNКА meet-in-the-middle дп математика Перебор теория чисел *3200 Если вы дошли до этой задачи, вы всё равно вряд ли станете читать легенду... Вам дана бинарная строка $\text{[math]}$ и целое число $\text{[math]}$ . Найдите количество целых k, 0 ≤ k < N, таких что для всех i = 0, 1, ..., m - 1 $\text{[math]}$ Выведите ответ по модулю 10⁹ + 7. Входные данные В первой строке входного файла содержится строка s, состоящая из символов 0 и 1 (1 ≤ \|s\| ≤ 40). В следующей строке содержится целое число n (1 ≤ n ≤ 5·10⁵). В каждой из следующих n строк содержатся два разделённых пробелом целых числа p_i, α_i (1 ≤ p_i, α_i ≤ 10⁹, p_i простое). Все p_i различны. Выходные данные Едиственное число — ответ на задачу.
D. k-Интересные пары чисел особая задача meet-in-the-middle битмаски Перебор 1700 У Васи есть последовательность, состоящая из n целых чисел. Вася считает пару чисел x и y k-интересной, если их двоичное представление отличается друг от друга ровно в k битах. Например, если k = 2, то пара чисел x = 5 и y = 3 является k-интересной, так как двоичные представления x=101 и y=011 отличаются ровно в двух битах. Васе стало интересно, сколько в его последовательности существует пар индексов (i, j) таких, что i < j и пара чисел a_i и a_j является k-интересной. Перед вами стоит задача помочь Васе и определить это количество. Входные данные В первой строке следует два целых числа n и k (2 ≤ n ≤ 10⁵, 0 ≤ k ≤ 14) — количество чисел в последовательности Васи и количество битов, в которых должны отличаться числа в k-интересной паре. Во второй строке следует последовательность a₁, a₂, ..., a_n (0 ≤ a_i ≤ 10⁴), которая есть у Васи. Выходные данные Выведите количество пар (i, j) таких, что i < j и пара чисел a_i и a_j является k-интересной. Примечание В первом примере существует 4 k-интересные пары: (1, 3), (1, 4), (2, 3), (2, 4). Во втором примере k = 0. Следовательно, числа в любой k-интересной паре должны быть равны между собой. Таким образом, для второго примера существует 6 k-интересных пар: (1, 5), (1, 6), (2, 3), (2, 4), (3, 4), (5, 6).
D. Расширение поля meet-in-the-middle дп Перебор *2100 Одна из игр, которыми увлекается Аркадий, происходит на прямоугольном участке. В процессе игры Аркадий может покупать расширения для своего участка, каждое расширение в несколько раз увеличивает любую из двух сторон его участка. Формально, есть n расширений, i-е из них позволяет увеличить длину или ширину (по выбору Аркадия) участка в a_i раз. Каждое расширение можно использовать не более одного раза, расширения можно использовать в любом порядке. Сейчас участок Аркадия имеет размер h × w. Он хочет его расширить так, чтобы возможно было разместить на участке прямоугольное поле размером a × b (вдоль или поперек, параллельно сторонам участка). Найдите минимальное число расширений, которое будет достаточно Аркадию для достижения своей цели. Входные данные В первой строке следуют пять целых чисел a, b, h, w и n (1 ≤ a, b, h, w, n ≤ 100 000) — размеры поля, которое нужно разместить на участке, размеры участка, а также количество доступных расширений. Во второй строке следует последовательность n целых чисел a₁, a₂, ..., a_n (2 ≤ a_i ≤ 100 000), где a_i равно количеству раз, в которое может быть увеличена сторона при применении к ней i-го расширений. Выходные данные Выведите минимальное число расширений, которое будет достаточно Аркадию для достижения своей цели. Если невозможно поместить поле на участок после использования всех расширений, выведите -1. Если поле изначально помещается на участок, выведите 0. Примечание В первом примере достаточно использовать любое из доступных расширений. Например, можно увеличить h в 5 раз, использовав второе расширение. Тогда h станет равно 10 и станет возможно поместить поле на получившийся расширенный участок.
E. Мать драконов meet-in-the-middle графы математика Перебор *2700 В Королевстве Ланнистеров n замков и несколько стен, соединяющих два замка, никакие два замка не соединены более, чем одной стеной, ни одна стена не соединяет замок с собой. Сир Джейме Ланнистер узнал, что Дейенерис Таргариен собирается атаковать его королевство. Он хочет защитить свои владения. У него есть k литров странной жидости. Он хочет распределить эту жидкость между замками так, чтобы каждый замок содержал некоторое количество жидкости (возможно, нулевое или нецелое количество литров). После этого стабильность стены, соединяющей замки a и b, содержащие x и y литров жидкости, соответственно, равна x·y. Ваша задача — найти максимальную возможную сумму стабильностей стен, которую Сир Джейме Ланнистер сможет достичь Входные данные Первая строка содержит два целых числа n и k (1 ≤ n ≤ 40, 1 ≤ k ≤ 1000). Далее следует n строк. В i-й из них содержится n целых чисел a_i, 1, a_i, 2, ..., a_i, n ( $\text{[math]}$ ). Если замки i и j соединены стеной, a_i, j = 1. В противном случае оно равно 0. Гарантируется, что a_i, j = a_j, i и a_i, i = 0 для всех 1 ≤ i, j ≤ n. Выходные данные Выведите одно число — максимальную возможную сумму стабильностей стен, которую Сир Джейме Ланнистер сможет достичь. Ваш ответ будет считаться правильным, если его абсолютная или относительная точность не превосходит 10^- 6. А именно, если ваш ответ равен a, а ответ жюри равен b, то ваш ответ будет зачтен, если $\text{[math]}$ . Примечание В первом примере, если замки 1, 2, 3 содержат 0.5, 0.5, 0 литров жидкости, соответственно, ответ равен 0.25. Во втором примере, если замки 1, 2, 3, 4 содержат 1.0, 1.0, 1.0, 1.0 литров жидкости, ответ равен 4.0.
F. Яичная рулетка meet-in-the-middle битмаски математика Перебор разделяй и властвуй *3300 В Яичную рулетку играют два игрока. Изначально 2R сырых яйца и 2C вареных яйца кладутся в коробку в случайном порядке. Яйца все еще в скорлупе, поэтому невозможно отличить сырое яйцо от вареного. По одному игроки выбирают одно яйцо и разбивают его о свой лоб. Если яйцо было вареное, ничего особенного не произойдет, но если оно было сырое, то оно все испачкает. Такое продолжается до тех пор, пока один из игроков не разобьет R сырых яиц. В этот момент игра заканчивается, этот игрок объявляется проигравшим, а его соперник — победителем. Порядок, в котором ходят игроки, может быть представлен как строка из букв «A» и «B», где i-й символ обозначает игрока, который будет выбирать i-е яйцо. Традиционно игроки ходят по очереди, то есть, они следуют порядку «ABABAB...». Это не очень честно, так как второй игрок будет выигрывать чаще, чем первый. Мы хотим, чтобы вы нашли более честный порядок ходов. Определим нечестность порядка как модуль разности между вероятностью победы первого игрока и вероятностью победы второго игрока. Нам интересны порядки, в которых нечестность является минимально возможной. Мы считаем порядок корректным, если в нем одинаковое количество букв «A» и «B». Вам будет дана строка S длины 2(R + C), содержащая только символы «A», «B» и «?». Порядок подходит под S, если он отличается от S только в позициях, где S содержит «?». Среди корректных порядков, минимизирующих нечестность, сколько подходят под S? Входные данные Первая строка содержит целые числа R и C (1 ≤ R, C ≤ 20, R + C ≤ 30). Вторая строка содержит строку S, имеющею длину 2(R + C) и состоящую только из символов «A», «B», «?». Выходные данные Выведите количество корректных порядков, которые минимизируют нечестность и подходят под S. Примечание В первом тесте из примере минимальная нечестность равна 0, а порядки, минимизирующие ее, это «ABBA» и «BAAB», но ни один из них не подходит под S. Заметьте, что порядок «ABBB» также имеет нечестность 0, но он не является корректным, так как не содержит одинаковое число «A» и «B». Во втором примере единственно подходящим порядком является «BBAAABABABBA».
E. Максимальная подпоследовательность meet-in-the-middle битмаски разделяй и властвуй *1800 Вам дан массив a, состоящий из n целых чисел и целое число m. Выберите последовательность позиций b₁, b₂, ..., b_k (1 ≤ b₁ < b₂ < ... < b_k ≤ n) такую, чтобы значение $\text{[math]}$ было максимально. Выбранная подследовательность может быть пустой. Подсчитайте максимальное возможное значение $\text{[math]}$ . Входные данные В первой строке записаны два целых числа n и m (1 ≤ n ≤ 35, 1 ≤ m ≤ 10⁹). Во второй строке записаны n целых чисел a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹). Выходные данные Выведите максимальное возможное значение $\text{[math]}$ . Примечание В первом примере можно выбрать последовательность b = {1, 2}, чтобы сумма $\text{[math]}$ была равна 7 (равна 3 по модулю 4). Во втором примере можете выбрать последовательность b = {3}.
E. Простой подарок meet-in-the-middle Бинарный поиск математика поиск в глубину и подобное теория чисел *2400 — Мужик, у тебя простые числа есть? — Нету. — На, мужик, простые числа. Пингвин В отличие от Гриши, который вел себя хорошо, Олег за весь год так и не научился решать задачи на теорию чисел. Поэтому вместо Деда Мороза к нему пришел его сокомандник Андрей и торжественно вручил ему множество из n различных простых чисел вместе с простой задачей: Олегу необходимо найти k-е в порядке возрастания положительное целое число, среди простых делителей которого встречаются числа только из этого множества. Входные данные В первой строке задано целое число n (1 ≤ n ≤ 16) — количество чисел во множестве. Во второй строке n различных простых чисел p₁, p₂, ..., p_n (2 ≤ p_i ≤ 100) — числа во множестве. Гарантируется, что числа идут в порядке возрастания. В третьей строке задано число k (1 ≤ k). Гарантируется, что k-е в порядке возрастания положительное целое число, среди простых делителей которого встречаются числа только из данного множества не превосходит 10¹⁸. Выходные данные Выведите k-е в порядке возрастания число, удовлетворяющее условию. Гарантируется, что оно не превосходит 10¹⁸. Примечание Для первого примера последовательность с простыми делителями из набора {2, 3, 5} выглядит так: (1, 2, 3, 4, 5, 6, 8, ...) Седьмым по счету числом (в 1-индексации) как раз и будет восьмерка.
E. Number Clicker meet-in-the-middle графы разделяй и властвуй теория чисел *2700 Аллен играет в Number Clicker на телефоне. Он начинает с целого числа $u$ на экране. Каждую секунду он нажимает одну из трех кнопок: Изменить $u \to u+1 \pmod{p}$. Изменить $u \to u+p-1 \pmod{p}$. Изменить $u \to u^{p-2} \pmod{p}$. Аллен хочет нажать на кнопки не более 200 раз так, чтобы получить на экране число $v$. Помогите ему! Входные данные Первая строка содержит три целых числа: $u, v, p$ ($0 \le u, v \le p-1$, $3 \le p \le 10^9 + 9$). Гарантируется, что $p$ — простое. Выходные данные В первой строке выведите одно целое число $\ell$ — количество нажатий кнопок. Во второй строке выведите целые числа $c_1, \dots, c_\ell$ — кнопки, которые должен нажать Аллен. Для всех $1 \le i \le \ell$ должно выполняться $1 \le c_i \le 3$. Можно показать, что ответ всегда существует. Примечание В первом примере число на экране меняется следующим образом: $1 \to 2 \to 3$. Во втором примере число на экране меняется следующим образом: $3 \to 2$.
Robot Instructions meet-in-the-middle Беси учится управлять роботом, который она недавно получила в подарок. Робот начинает в точке $(0, 0)$ координатной плоскости и Беси хочет привести робота в точку $(x_g, y_g)$. Изначально у Беси есть список из $N$ ($1\le N\le 40$) инструкций для робота, $i$-ая из которых перемещает робота на $x_i$ единиц вправо и на $y_i$ единиц вверх (или влево и вниз, если $x_i$ и $y_i$ отрицательные, соответственно). Для каждого $K$ от $1$ to $N$, вычислите количество способов, которыми Беси может выбрать $K$ инструкций из исходного списка так, что после применения этих $K$ инструкций, робот окажется в точке $(x_g, y_g)$. Замечание: лимиты на время и память в этой задаче увеличены вдвое до 4s и 512MB, относительно значений по умолчанию. ФОРМАТ ВВОДА (с клавиатуры / stdin): Первая строка содержит $N$. Следующая строка содержит $x_g$ и $y_g$, каждое в интервале $-10^9 \ldots 10^9$. Последующие $N$ описывают инструкции. Каждая строка содержит два целых числа $x_i$ и $y_i$, также в интервале $-10^9 \ldots 10^9$. Гарантируется, что $(x_g,y_g)\neq (0,0)$ и $(x_i,y_i)\neq (0,0)$ для всех $i$. ФОРМАТ ВЫВОДА (на экран / stdout): Выведите $N$ строк, количество способов, которыми Беси может выбрать $K$ инструкций из списка оригинальных $N$, для каждого $K$ от $1$ до $N$.
Balanced Cow Subsets meet-in-the-middle У Фермера Джона есть N cows (2 <= N <= 20), и корова I производит M(i) единиц молока ежедневно (1 <= M(i) <= 100,000,000). ФД хочет рационализировать процесс ежедневной дойки коров, поэтому он установил новый доильный аппарат в амбаре. Есть одно НО – аппарат работает, только если коровы на левой стороне амбара имеют такое же общее количество молока, как и коровы на правой стороне амбара. Назовем подмножество коров «сбалансированным», если оно может быть разбито на две группы, имеющие равные суммарные надои молока. ФД хочет, чтобы Вы посчитали, сколько подмножеств из его N коров сбалансированы. PROBLEM NAME: subsets Формат входных данных * Строка 1: Целое N. * Строки 2..1+N: Строка i+1 содержит M(i). Формат выходных данных * Строка 1: Количество сбалансированных подмножеств коров. Примечание Подмножество {1,2,3} может быть разбито на {1,2} и {3}. Подмножество {1,3,4} может быть разбито на {1,3} и {4}. Подмножество {1,2,3,4} может быть разбито на {1,4} и {2,3}.
Красивые разбиения meet-in-the-middle битмаски Напомним, что простое число — это целое число, которое делится ровно на два целых числа: на единицу и на себя. Последовательность простых чисел начинается с $2, 3, 5, \ldots$. Рассмотрим первые $n$ простых чисел. Давайте разделим их на две части $A$ и $B$ так, чтобы каждое простое число принадлежало ровно одной из этих двух частей. Обозначим произведение всех простых чисел в $A$ как $a$, а произведение всех простых чисел в $B$ как $b$. Произведение чисел в пустом множестве будем считать равным $1$. Будем называть разбиение красивым, если $a < b$ и $b-a$ минимальное возможное. Дано $n$, найдите красивое разбиение множества первых $n$ простых чисел и выведите соответствующее значение $a$. Формат входных данных Входные данные содержит целое число $n$ на отдельной строке ($1 \le n \le 30$). Формат выходных данных Выведите значение $a$ в красивом разбиении множества первых $n$ простых чисел.


F. Xor-пути meet-in-the-middle битмаски дп Перебор *2100 Задано прямоугольное поле размера \(n \times m\). В каждой клетке записано целое число; число, записанное в клетке (\(i, j\)) равно \(a_{i, j}\). Ваша задача — посчитать количество путей из клетки (\(1, 1\)) в клетку (\(n, m\)), удовлетворяющих следующим условиям: Из клетки можно перемещаться только вниз или только вправо. Более формально, из клетки (\(i, j\)) можно переместиться в клетку (\(i, j + 1\)) или в клетку (\(i + 1, j\)). Клетка, в которую совершается перемещение, не может находиться за пределами поля. Xor всех чисел на пути из клетки (\(1, 1\)) в клетку (\(n, m\)) должен быть равен \(k\) (xor это побитовое исключающее ИЛИ, эта операция представлена как '^' в Java или C++ и "xor" в Pascal). Найдите количество подходящих путей для заданного поля. Входные данные Первая строка входных данных содержит три целых числа \(n\), \(m\) и \(k\) (\(1 \le n, m \le 20\), \(0 \le k \le 10^{18}\)) — высота и ширина поля, и число \(k\). Следующие \(n\) строк содержат по \(m\) целых чисел каждая, где \(j\)-й элемент \(i\)-й строки равен \(a_{i, j}\) (\(0 \le a_{i, j} \le 10^{18}\)). Выходные данные Выведите одно целое число — количество путей из (\(1, 1\)) в (\(n, m\)) с xor всех чисел на пути равным \(k\). Примечание Все пути из первого тестового примера: \((1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 2) \rightarrow (3, 3)\); \((1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3)\); \((1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3)\). Все пути из второго тестового примера: \((1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 2) \rightarrow (3, 3) \rightarrow (3, 4)\); \((1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3) \rightarrow (3, 4)\); \((1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (2, 4) \rightarrow (3, 4)\); \((1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3) \rightarrow (3, 4)\); \((1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3) \rightarrow (3, 4)\).
D. Загадочное преступление meet-in-the-middle Комбинаторика математика Перебор *1700 Ацингел — достаточно маленький городок. В этом городке был всего один доктор — Мисс Ада. Она была очень дружелюбной и никто никогда не говорил про неё ничего плохого. Так что кто мог подумать, что Аду найдут мёртвой в собственном доме? Мистер Гаври, известный во всём мире детектив, был назначен найти преступника. Он опросил \(m\) соседей Ады о клиентах, которые посетили её в тот злосчастный день. Давайте пронумеруем этих клиентов от \(1\) до \(n\). Свидетельством каждого соседа является перестановка этих чисел, которая описывает порядок, в котором этот сосед видел клиентов приходящими к Аде. Однако некоторые факты выглядят достаточно подозрительно — как могло быть, что, согласно некоторым перестановкам некоторые клиенты были замечены утром, а согласно другим — вечером? «Утром некоторые из соседей скорее всего спали! — подумал Гаври, — А вечером слишком темно, чтобы видеть лица людей...». Теперь он хочет удалить из каждой перестановки некоторый префикс и некоторый суффикс (возможно, пустые) так, что оставшиеся части будут не пусты и равны друг другу. Возможно, часть потенциальных преступников пропадёт, но хотя бы не будет противоречий в свидетельствах соседей. Сколькими способами он может это сделать? Два способа называются разными, если в них отличается оставшаяся общая часть. Входные данные Первая строка содержит два целых числа \(n\) и \(m\) (\(1 \le n \le 100\,000\), \(1 \le m \le 10\)) — количество подозреваемых и количество опрошенных соседей. Каждая из следующих \(m\) строк содержит \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le n\)). Гарантируется, что эти числа образуют перестановку (то есть каждое число от \(1\) до \(n\) встречается ровно один раз). Выходные данные Выведите одно целое число — количество способов удалить из каждой перестановки некоторый префикс и суффикс (возможно, пустые) так, что оставшаяся часть была бы равной и непустой. Примечание В первом примере общей частью может быть \([1]\), \([2]\), \([3]\) и \([2, 3]\). Во втором и третьем примерах можно оставлять только общие части из \(1\) элемента.
E. Помочь Хиасату meet-in-the-middle битмаски дп Перебор *2200 Хиасат недавно зарегистрировал новый аккаут на сайте NeckoForces и, как только его друзья об этом узнали, каждый из них захотел, чтобы его имя было названием хендла профиля Хиасата. К счастью для Хиасата, он может менять свой профиль в некоторые моменты времени. Также он знает моменты времени, когда его друзья будут заходить на его страницу. Формально, дана последовательность событий двух видов: \(1\) — Хиасат может поменять свой хендл. \(2\) \(s\) — друг \(s\) посещает профиль Хиасата. Друг \(s\) будет счастлив, если каждый раз, когда он посетит страницу Хиасата, его хендл будет равен \(s\). Хиасат просит вас помочь ему, выясните наибольшее количество счастливых друзей, которого можно добиться. Входные данные Первая строка содержит два целых числа \(n\) и \(m\) (\(1 \le n \le 10^5, 1 \le m \le 40\)) — количество событий и количество друзей. Затем следуют \(n\) строк, задающих событие одно из двух видов: \(1\) — Хиасат может поменять свой хендл. \(2\) \(s\) — друг \(s\) (\(1 \le \|s\| \le 40\)) посещает профиль Хиасата. Гарантируется, что имя каждого друга состоит только из строчных латинских букв. Гарантируется, что первое событие обязательно первого типа, и что каждый друг посетит профиль Хиасата хотя бы один раз. Выходные данные Выведите одно целое число — наибольшее число счастливых друзей. Примечание В первом примере, оптимально поменять хендл на «motarack» в первом событие и на «light» в четвёртом. Таким образом, «motarack» и «light» будут счастливы, а «mike» — нет. Во втором примере можно выбрать «alice», «bob» или «tanyaromanova», и ровно этот друг и будет счастлив.
C. Кубворд *особая задача meet-in-the-middle дп Перебор Кубворд — особый вид кроссворда. Для построения кубворда сначала выбирается положительное целое число \(a\) — длина стороны куба. Затем строится большой куб, состоящий из \(a \times a \times a\) единичных кубиков. У большого куба 12 ребер. После этого выкидываются все единичные кубики, которые не касаются ребер большого куба. Рисунок ниже показывает, что получится при \(a=6\). $\text{[math]}$ Наконец, вы пишете по одной букве в каждый единичный кубик. Вдоль каждого ребра большого куба должно получиться осмысленное слово. Буквы на любом ребре могут быть прочитаны в любом направлении, и достаточно, чтобы хотя бы в одном из направлений получилось осмысленное слово. Рисунок ниже показывает фигуру при \(a=6\), где в некоторые единичные кубики уже записаны буквы. Уже можно прочитать слова «SUBMIT», «ACCEPT» и «TURING» вдоль трех ребер большого куба. $\text{[math]}$ Вам дан список осмысленных слов. Каждое слово из этого списка может сколько угодно раз читаться на ребрах кубворда. Найдите число различных кубвордов, которые можно составить из этих слов, по модулю \(998,244,353\). Если один кубворд может быть получен из другого поворотом или отражением, они считаются различными. Входные данные Первая строка содержит одно целое число \(n\) (\(1 \leq n \leq 100,000\)) – количество слов. Далее следуют \(n\) строк. Каждая из этих строк содержит одно слово, которое может присутствовать на ребрах большого куба. Длина каждого слова находится в пределах от 3 до 10 включительно. Гарантируется, что все слова различны. Выходные данные Выведите одно целое число — количество различных кубвордов из данных слов по модулю \(998,244,353\). Система оценки Подзадача 1 (21 балл): слова содержат только буквы «a» - «f» (строчные) Подзадача 2 (29 баллов): слова содержат только буквы «a» - «p» (строчные) Подзадача 3 (34 балла): слова содержат только буквы «a» - «p» (строчные) и «A» - «P» (заглавные) Подзадача 4 (16 баллов): слова содержат только буквы «a» - «z» (строчные), «A» - «Z» (заглавные) и цифры «0» - «9» Примечание В первом примере единственная возможность составить кубворд — написать слово «radar» на всех ребрах. Во втором примере есть два различных кубворда, которые получаются друг из друга поворотом: слово «robot» на всех ребрах, и разница лишь в том, содержит ли левый нижний передний угол букву «r» или «t». Третий пример похож на второй. То, что мы можем читать слова в обоих направлениях, не изменяет ответ. В четвертом примере есть один кубворд со словом «bob» на каждом ребре. Кроме того, есть \(2^{12} = 4096\) кубов со словом «baobab» на каждом ребре: для каждого из 12 ребер есть два возможных направления, в которых можно написать слово «baobab».
G. Граф и числа meet-in-the-middle битмаски дп Комбинаторика Перебор *2900 Вам задан неориентированный граф из \(n\) вершин и \(m\) ребер. Вы должны написать число на каждой вершине графа, каждое число должно быть равно \(0\) или \(1\). После этого на каждом ребре будет записана сумма чисел на двух вершинах, инцидентных этому ребру. Вы должны выбрать числа таким образом, чтобы было хотя бы одно ребро с числом \(0\), хотя бы одно ребро с числом \(1\) и хотя бы одно ребро с числом \(2\). Сколько способов так расставить числа? Два способа различны, если существует хотя бы одна вершина, на которой в разных способах записаны разные числа. Входные данные В первой строке заданы два целых числа \(n\) и \(m\) (\(1 \le n \le 40\), \(0 \le m \le \frac{n(n - 1)}{2}\)) — количество вершин и ребер, соответственно. Затем следуют \(m\) строк, в каждой из которых записаны два целых числа \(x_i\) и \(y_i\) (\(1 \le x_i, y_i \le n\), \(x_i \ne y_i\)) — вершины, соединяемые \(i\)-м ребром. Гарантируется, что между каждой парой вершин существует не более одного ребра. Выходные данные Выведите одно целое число — количество способов так записать числа на вершинах, что есть хотя бы одно ребро с числом \(0\), хотя бы одно ребро с числом \(1\) и хотя бы одно ребро с числом \(2\).
C2. Хорошие числа (сложная версия) meet-in-the-middle Бинарный поиск жадные алгоритмы математика *1500 Единственное отличие между простой и сложной версиями — максимальное значение \(n\). Вам дано положительное целое число \(n\). Вы очень любите хорошие числа, поэтому вам хочется найти минимальное хорошее число, большее или равное \(n\). Положительное число называется хорошим, если оно может быть представлено в виде суммы различных степеней \(3\) (т.е. повторения степеней \(3\) запрещены). Например: \(30\) — хорошее число: \(30 = 3^3 + 3^1\), \(1\) — хорошее число: \(1 = 3^0\), \(12\) — хорошее число: \(12 = 3^2 + 3^1\), но \(2\) не является хорошим числом: вы не можете представить его в виде суммы различных степеней \(3\) (\(2 = 3^0 + 3^0\)), \(19\) не является хорошим числом: вы не можете представить его в виде суммы различных степеней \(3\) (например, представления \(19 = 3^2 + 3^2 + 3^0 = 3^2 + 3^1 + 3^1 + 3^1 + 3^0\) не являются корректными), \(20\) тоже не является хорошим числом: вы не можете представить его в виде суммы различных степеней \(3\) (например, представление \(20 = 3^2 + 3^2 + 3^0 + 3^0\) не является корректным). Обратите внимание, что существуют и другие представления \(19\) и \(20\) в качестве сумм степеней \(3\), но ни одно из них не состоит из различных степеней \(3\). Для заданного положительного числа \(n\) найдите наименьшее \(m\) (\(n \le m\)) такое, что \(m\) — хорошее число. Вам необходимо ответить на \(q\) независимых запросов. Входные данные Первая строка входных данных содержит одно целое число \(q\) (\(1 \le q \le 500\)) — количество запросов. Затем следуют \(q\) запросов. Единственная строка запроса содержит одно целое число \(n\) (\(1 \le n \le 10^{18}\)). Выходные данные Для каждого запроса выведите наименьшее число \(m\) (где \(n \le m\)) такое, что \(m\) —хорошее число.
F. Сделай их похожими meet-in-the-middle битмаски Перебор хэши *2400 Назовем два числа похожими, если в их двоичных представлениях одинаковое количество цифр равно \(1\). Например: \(2\) и \(4\) похожи (двоичные представления — \(10\) и \(100\)); \(1337\) и \(4213\) похожи (двоичные представления — \(10100111001\) и \(1000001110101\)); \(3\) и \(2\) не похожи (двоичные представления — \(11\) и \(10\)); \(42\) и \(13\) похожи (двоичные представления — \(101010\) и \(1101\)). Вам задан массив из \(n\) целых чисел \(a_1\), \(a_2\), ..., \(a_n\). Вы должны выбрать неотрицательное целое число \(x\), после чего вы получите новый массив из \(n\) чисел \(b_1\), \(b_2\), ..., \(b_n\), где \(b_i = a_i \oplus x\) (\(\oplus\) обозначает операцию побитового исключающего ИЛИ). Можно ли получить такой массив \(b\), в котором все числа похожи друг на друга? Входные данные В первой строке задано одно целое число \(n\) (\(2 \le n \le 100\)). Во второй строке заданы \(n\) целых чисел \(a_1\), \(a_2\), ..., \(a_n\) (\(0 \le a_i \le 2^{30} - 1\)). Выходные данные Если нельзя выбрать такой \(x\), что все элементы в полученном массиве будут похожи друг на друга, выведите \(-1\). Иначе выведите любое неотрицательное целое число, не превосходящее \(2^{30} - 1\), которое можно использовать как \(x\) таким образом, что все числа в полученном массиве будут похожи друг на друга.
C. Вы все уже победители! meet-in-the-middle Бинарный поиск математика теория чисел *1400 На всеми известной тестирующей системе MathForces устраивается розыгрыш \(n\) единиц рейтинга. Раздача рейтинга будет происходить по следующему алгоритму: если в мероприятии принимает участие \(k\) участников, то \(n\) рейтинга поровну распределяется между ними и округляется в сторону ближайшего меньшего целого числа. По окончании распределения может остаться неиспользованный рейтинг — он не достаётся никому из участников. К примеру, если \(n = 5\) и \(k = 3\), то каждый участник получит \(1\) единицу рейтинга, а также \(2\) единицы рейтинга останутся неиспользованными. Если же \(n = 5\), а \(k = 6\), то ни у кого из участников не увеличится рейтинг. Вася участвует в этом розыгрыше рейтинга, но не владеет информацией об общем количестве участников этого мероприятия. Поэтому он хочет узнать, какие различные значения приращения рейтинга он может получить в результате этого розыгрыша, и просит Вас о помощи. Например, если \(n=5\), то искомый ответ равен последовательности \(0, 1, 2, 5\). Каждое из значений последовательности (и только они) может быть получено как \(\lfloor n/k \rfloor\) для некоторое подходящего целого положительного \(k\) (где \(\lfloor x \rfloor\) — округлённое вниз значение \(x\)): \(0 = \lfloor 5/7 \rfloor\), \(1 = \lfloor 5/5 \rfloor\), \(2 = \lfloor 5/2 \rfloor\), \(5 = \lfloor 5/1 \rfloor\). Напишите программу, которая по заданному \(n\) находит последовательность всех возможных приращений рейтинга. Входные данные В первой строке входных данных записано целое число \(t\) (\(1 \le t \le 10\)) — количество наборов входных данных в тесте. Далее следуют описания \(t\) наборов входных данных, по одному описанию в строке. Каждая строка содержит целое число \(n\) (\(1 \le n \le 10^9\)) — суммарное количество разыгрываемого рейтинга. Выходные данные Выведите ответы на \(t\) заданных наборов входных данных. Каждый ответ должен состоять из двух строк. В первой строке выведите число \(m\) — количество различных значений приращения рейтинга, которые может получить Вася. В следующей строке выведите \(m\) различных чисел — сами значения приращения рейтинга в порядке возрастания.
H. Красно-синий граф meet-in-the-middle графы дп математика матрицы *3400 Дан ориентированный граф из \(n\) вершин, пронумерованных от \(1\) до \(n\), в котором из каждой вершины (кроме \(n\)) исходит две дуги, красная и синяя. В любой момент времени ровно одна исходящая дуга является активной для каждой вершины. Изначально все синие дуги активны, а в вершине \(1\) находится фишка. В начале каждой секунды у вершины, в которой стоит фишка, меняется активная дуга. Затем фишка перемещается по активной дуге. Когда фишка достигает вершины \(n\), она останавливается. Гарантируется, что вершина \(n\) достижима по дугам из всех остальных вершин графа. Вам задаются \(q\) запросов, в каждом из которых описывается состояние графа — пара \((v, s)\) следующего вида: \(v\) — вершина, в которой находится фишка; \(s\) — строка из \(n - 1\) символов. \(i\)-й символ обозначает, какая дуга, ведущая из \(i\), активна (красная, если символ равен 'R', или синяя, если символ — 'B'). Для каждого запроса определите, достижимо ли заданное состояние из стартового, и если да — когда такое состояние графа появится в первый раз. Обратите внимание, что заданные две операции неразрывны между собой — состояние не считается достигнутым, если оно появляется после изменения активной дуги, но до того, как фишку переместили по дуге. Входные данные В первой строке задано одно целое число \(n\) (\(2 \leq n \leq 58\)) — количество вершин. Далее следуют \(n-1\) строк, \(i\)-я из которых содержит два целых числа \(b_i\) и \(r_i\) (\(1 \leq b_i, r_i \leq n\)), обозначающих синюю дугу \((i, b_i)\) и красную дугу \((i, r_i)\), соответственно. Гарантируется, что вершина \(n\) достижима из всех остальных. Следующая строка содержит одно целое число \(q\) (\(1 \leq q \leq 5000\)) — количество запросов. Затем следуют \(q\) строк с запросами. \(j\)-я из них содержит целое число \(v\) (\(1 \leq v < n\)) и строку \(s\) из \(n-1\) символов, каждый из которых либо 'R', либо 'B'. \(i\)-й из этих символов равен 'R', если красная дуга, ведущая из вершины \(i\), активна, иначе этот символ равен 'B'. Выходные данные Выведите \(q\) чисел, каждое из которых содержит ответ на один запрос. Если состояние в \(i\)-м запросе недостижимо, выведите \(-1\). Иначе выведите \(t_i\) — первый момент времени, когда это состояние появилось (выводите время в секундах, начиная отсчет с секунды \(0\), в которую появилось стартовое состояние). Примечание На картине изображен граф из первого примера. $\text{[math]}$ Первые \(19\) запросов показывают перемещение фишки. После \(19\)-го шага фишка достигает вершины \(6\). Последние два запроса соответствуют недостижимым состояниям.
F1. Мудрецы (упрощенная версия) meet-in-the-middle битмаски дп Перебор *2600 Это упрощенная версия задачи. Две версии отличаются ограничением на число мудрецов и ограничением по времени. Вы можете взламывать по этой задаче только если обе версии решены. \(n\) мудрецов живут в красивом городе. Некоторые из них знают друг друга. Для всех возможных \(n!\) перестановок \(p_1, p_2, \ldots, p_n\) мудрецов, построим бинарную строку длины \(n-1\): для всех \(1 \leq i < n\) положим \(s_i=1\) если мудрецы \(p_i\) и \(p_{i+1}\) знают друг друга, и \(s_i=0\) иначе. Для всех \(2^{n-1}\) возможных бинарных строк, найдите число перестановок, при которых получается такая бинарная строка. Входные данные В первой строке записано одно целое число \(n\) (\(2 \leq n \leq 14)\) — количество мудрецов в городе. Следующие \(n\) строк содержат бинарные строки, по \(n\) символов в каждой, \(j\)-й символ в \(i\)-й строке равен «1» если мудрец \(i\) знает мудреца \(j\), и равен «0» иначе. Гарантируется, что если \(i\)-й мудрец знает \(j\)-го мудреца, то \(j\)-й мудрец знает \(i\)-го мудреца, и никакой мудрец не знает сам себя. Выходные данные Выведите \(2^{n-1}\) целых чисел, разделенных пробелами. Для каждого \(0 \leq x < 2^{n-1}\): Рассмотрим такую строку \(s\) длины \(n-1\), что \(s_i = \lfloor \frac{x}{2^{i-1}} \rfloor \bmod 2\) для \(1 \leq i \leq n - 1\). \((x+1)\)-е число должно быть необходимому ответу для \(s\). Примечание В первом тесте все мудрецы знакомы, соответственно для всех перестановок получается строка \(11\). Во втором тесте Если \(p = \{1, 2, 3, 4\}\), строка будет равна \(101\), потому что мудрецы \(1\) и \(2\) знакомы, \(2\) и \(3\) не знакомы, \(3\) и \(4\) знакомы; Если \(p = \{4, 1, 2, 3\}\), строка будет равна \(110\), потому что мудрецы \(1\) и \(4\) не знакомы, \(1\) и \(2\) не знакомы, \(2\) и \(3\) не знакомы; Если \(p = \{1, 3, 2, 4\}\), строка будет равна \(000\), потому что мудрецы \(1\) и \(3\) не знакомы, \(3\) и \(2\) не знакомы, \(2\) и \(4\) не знакомы.
L. Light switches meet-in-the-middle *2600 Nikola owns a large warehouse which is illuminated by \(N\) light bulbs, numbered \(1\) to \(N\). At the exit of the warehouse, there are \(S\) light switches, numbered \(1\) to \(S\). Each switch swaps the on/off state for some light bulbs, so if a light bulb is off, flipping the switch turns it on, and if the light bulb is on, flipping the switch turns it off. At the end of the day, Nikola wants to turn all the lights off. To achieve this, he will flip some of the light switches at the exit of the warehouse, but since Nikola is lazy, he wants to flip the _minimum_ number of switches required to turn all the lights off. Since Nikola was not able to calculate the minimum number of switches, he asked you to help him. During a period of \(D\) days, Nikola noted which light bulbs were off and which were on at the end of each day. He wants you to tell him the minimum number of switches he needed to flip to turn all the lights off for each of the \(D\) days or tell him that it's impossible. Input First line contains three integers, \(N\), \(S\) and \(D\) (\(1 \leq N \leq 10^3\), \(1 \leq S \leq 30\), \(1 \leq D \leq 10^3\)) – representing number of light bulbs, the number of light switches, and the number of days respectively. The next \(S\) lines contain the description of each light switch as follows: The first number in the line, \(C_i\) (\(1 \leq C_i \leq N\)), represents the number of light bulbs for which the on/off state is swapped by light switch \(i\), the next \(C_i\) numbers (sorted in increasing order) represent the indices of those light bulbs. The next \(D\) lines contain the description of light bulbs for each day as follows: The first number in the line, \(T_i\) (\(1 \leq T_i \leq N\)), represents the number of light bulbs which are on at the end of day \(i\), the next \(T_i\) numbers (sorted in increasing order) represent the indices of those light bulbs. Output Print \(D\) lines, one for each day. In the \(i^{th}\) line, print the minimum number of switches that need to be flipped on day \(i\), or \(-1\) if it's impossible to turn all the lights off.
F. Омкар и Акмар meet-in-the-middle бпф геометрия игры китайская теорема об остатках Комбинаторика Конструктив математика строковые суфф. структуры *2600 Омкар и Акмар играют в игру на круговой доске с \(n\) (\(2 \leq n \leq 10^6\)) клетками. Клетки пронумерованы от \(1\) до \(n\), для каждой \(i\) (\(1 \leq i \leq n-1\)) клетка \(i\) соседствует с клеткой \(i+1\), а клетка \(1\) соседствует с клеткой \(n\). Изначально каждая клетка пуста. Омкар и Акмар по очереди выкладывают на доску букву A или B, причем Акмар ходит первым. Буква должна быть помещена на пустую клетку. Кроме того, буква не может быть помещена в такую клетку, что соседняя клетка содержит ту же букву. Игрок проигрывает, когда наступает его очередь и больше нет допустимых ходов. Выведите количество возможных различных игр, в которых оба игрока играют оптимально по модулю \(10^9+7\). Обратите внимание, что мы рассматриваем только те партии, в которых кто-то из игроков проиграл, и не осталось ни одного допустимого хода. Две игры считаются разными, если количества ходов в них отличаются, или на каком-то ходу буква или номер клетки, на которую ставится буква, были разными. Ход считается оптимальным, если он максимизирует шансы игрока на победу, предполагая, что другой игрок также играет оптимально. Более формально, если игрок, чья очередь ходить, имеет выигрышную стратегию, он должен сделать ход, после которого у него останется выигрышная стратегия. Если же у него ее нет, то он может сделать любой ход. Входные данные Первая строка будет содержать целое число \(n\) (\(2 \leq n \leq 10^6\)) — количество клеток на доске. Выходные данные Выведите одно целое число, — количество возможных различных игр, в которых оба игрока играют оптимально по модулю \(10^9+7\). Примечание В первом примере первый игрок имеет \(4\) возможных хода. Независимо от того, как ходит первый игрок, у второго игрока есть ровно \(1\) возможный ход, поэтому существует \(4\) возможных игры.
E. Нижний уровень meet-in-the-middle Бинарный поиск графы жадные алгоритмы кратчайшие пути поиск в глубину и подобное *3000 В некоторой компьютерной игре игрок управляет героем, который характеризуется одним целочисленным параметром — силой. На текущем уровне герой попал в систему из \(n\) пещер, пронумерованных от \(1\) до \(n\), и \(m\) коридоров между ними. Каждый коридор соединяет две различные пещеры. Любые две пещеры соединены не более чем одним коридором. Из любой пещеры можно попасть в любую другую, двигаясь по коридорам. Герой начинает уровень в пещере \(1\), а в каждой из оставшихся пещер находится монстр. Герой может перемещаться между пещерами по коридорам. Если герой вышел из пещеры и начал движение по коридору, он обязан завершить его и дойти до противоположного конца коридора. По любому коридору герой может перемещаться в обоих направлениях. Однако герой не может использовать один и тот же коридор два раза подряд. Формально, если герой перешёл по коридору из пещеры \(i\) в пещеру \(j\), он не может сразу же направиться обратно в пещеру \(i\), но может направиться в любую другую пещеру, соединённую коридором с пещерой \(j\). Известно, что из любой пещеры выходит как минимум два коридора, поэтому герой никогда не попадёт в тупик даже с учётом предыдущего требования. Чтобы пройти уровень, герою нужно победить монстров во всех пещерах. Когда герой впервые зайдёт в пещеру, ему придётся драться с монстром в ней. Герой может победить монстра в пещере \(i\) только в том случае, если сила героя строго больше \(a_i\). В случае победы над монстром сила героя увеличится на \(b_i\). Если герой не может победить монстра, с которым он дерётся, игра заканчивается и игрок проигрывает. После того, как герой победит монстра в пещере \(i\), все последующие визиты в пещеру \(i\) не будут иметь последствий — монстра в этой пещере уже не будет, но и сила героя не будет изменяться. Найдите минимальную необходимую силу, с которой герой должен начать уровень, чтобы иметь возможность победить всех монстров и пройти уровень. Входные данные Во входных данных находятся несколько наборов входных данных. В первой строке задано одно целое число \(t\) (\(1 \le t \le 100\)) — количество наборов входных данных. Первая строка набора входных данных содержит два целых числа \(n\) и \(m\) (\(3 \le n \le 1000\); \(n \le m \le min(\frac{n(n-1)}{2}, 2000)\)) — число пещер и коридоров. Вторая строка содержит \(n-1\) целых чисел \(a_2, a_3, \ldots, a_n\) (\(1 \le a_i \le 10^9\)) — значения, с которыми сравнивается сила героя при битве с монстрами в пещерах \(2, 3, \ldots, n\). Третья строка содержит \(n-1\) целых чисел \(b_2, b_3, \ldots, b_n\) (\(1 \le b_i \le 10^9\)) — прибавки к силе героя за победу над монстрами в пещерах \(2, 3, \ldots, n\). Каждая из следующих \(m\) строк содержит два целых числа \(u_i\) и \(v_i\) (\(1 \le u_i, v_i \le n\); \(u_i \ne v_i\)) — номера пещер, соединённых коридором. Никакие две пещеры не соединены более чем одним коридором. Из любой пещеры можно попасть в любую другую, двигаясь по коридорам. Из любой пещеры выходит как минимум два коридора. Гарантируется, что сумма значений \(n\) по всем наборам входных данных не превосходит \(1000\), а сумма значений \(m\) по всем наборам входных данных не превосходит \(2000\). Выходные данные Для каждого набора входных данных выведите одно целое число — минимальную силу героя, необходимую для того, чтобы иметь возможность победить всех монстров и пройти уровень. Примечание В первом наборе входных данных герой может пройти уровень, начав с силы \(15\), следующим образом: перейти из пещеры \(1\) в пещеру \(2\): так как \(15 > 11\), герой побеждает монстра, сила героя увеличивается до \(15 + 8 = 23\); перейти из пещеры \(2\) в пещеру \(3\): так как \(23 > 22\), герой побеждает монстра, сила героя увеличивается до \(23 + 7 = 30\); перейти из пещеры \(3\) в пещеру \(4\): так как \(30 > 13\), герой побеждает монстра, сила героя увеличивается до \(30 + 5 = 35\). Во втором наборе входных данных ситуация аналогична, но прибавки к силе героя в пещерах \(2\) и \(4\) поменялись местами. Герой может использовать другой маршрут, \(1 \rightarrow 4 \rightarrow 3 \rightarrow 2\), и пройти уровень с начальной силой \(15\). В третьем наборе входных данных герой может пройти уровень, начав с силы \(19\), следующим образом: перейти из пещеры \(1\) в пещеру \(2\): так как \(19 > 10\), герой побеждает монстра, сила героя увеличивается до \(19 + 7 = 26\); перейти из пещеры \(2\) в пещеру \(4\): так как \(26 > 20\), герой побеждает монстра, сила героя увеличивается до \(26 + 10 = 36\); перейти из пещеры \(4\) в пещеру \(5\): так как \(36 > 30\), герой побеждает монстра, сила героя увеличивается до \(36 + 5 = 41\); перейти из пещеры \(5\) в пещеру \(2\): в этой пещере монстра уже нет, поэтому ничего не происходит; перейти из пещеры \(2\) в пещеру \(3\): так как \(41 > 40\), герой побеждает монстра, сила героя увеличивается до \(41 + 2 = 43\).
E. Восстановление турнирной таблицы meet-in-the-middle битмаски Перебор реализация хэши *2600 \(2^k\) команд участвуют в плей-офф турнире. Турнир состоит из \(2^k - 1\) игры. Они проводятся следующим образом: во-первых, команды делятся на пары: команда \(1\) играет против команды \(2\), команда \(3\) играет против команды \(4\) (именно в таком порядке) и так далее (таким образом, в этой фазе будет сыграно \(2^{k-1}\) игры). Когда команда проигрывает игру, она выбывает, и каждая игра приводит к выбыванию одной команды (нет ничьих). После этого остается \(2^{k-1}\) команд. Если остается только одна команда, она объявляется чемпионом; в противном случае играется еще \(2^{k-2}\) игр: в первой из них победитель игры «\(1\) против \(2\)» играет против победителя игры «\(3\) против \(4\)», затем победитель игры «\(5\) против \(6\)» играет против победителя игры «\(7\) против \(8\)» и так далее. Этот процесс повторяется до тех пор, пока не останется только одна команда. Место команды в турнире зависит от того, в какой фазе турнира она выбыла: команда-победитель турнира занимает место \(1\); команда, выбывшая в финале, занимает место \(2\); обе команды, выбывшие в полуфинале, занимают место \(3\); все команды, выбывшие в четвертьфинале, занимают место \(5\); все команды, выбывшие в 1/8 финала, занимают место \(9\), и так далее. Например, на этой картинке показан возможный ход турнира при \(k = 3\), а также итоговые места команд при таком ходе турнира: $\text{[math]}$ После окончания турнира, который проходил по этим правилам, его результаты были закодированы следующим образом. Пусть \(p_i\) — место, которое заняла \(i\)-я команда. Хэш турнира \(h\) считается по формуле \(h = (\sum \limits_{i=1}^{2^k} i \cdot A^{p_i}) \bmod 998244353\), где \(A\) — некоторое заданное целое число. К сожалению, из-за сбоя системы почти вся информация о прошедшем турнире была утеряна. Остались только значения \(k\), \(A\) и \(h\). Вам нужно по этим трем числам восстановить, какое место заняла какая команда (если это вообще возможно). Входные данные В единственной строке заданы три числа \(k\), \(A\) и \(h\) (\(1 \le k \le 5\); \(100 \le A \le 10^8\); \(0 \le h \le 998244352\)). Выходные данные Если распределения команд по местам, удовлетворяющего всем требованиям, не существует, выведите \(-1\). Иначе выведите \(2^k\) чисел, \(i\)-е из которых должно быть равно \(p_i\) (месту, занятому \(i\)-й командой). Обратите внимание: ваш ответ должен быть корректным вариантом результатов турнира, проводимого по описанным правилам; кроме того, структура турнира является фиксированной (например, команды \(1\) и \(2\) всегда играют между собой в первой фазе турнира). Если существует несколько способов восстановить места, занятые командами, выведите любой из них. Примечание Турнир из первого примера описан на картинке в условии. Для третьего примера, если выбрать расстановку команд по местам \([1, 2, 3, 3]\) (команда \(1\) занимает место \(1\), команда \(2\) занимает место \(2\), команды \(3\) и \(4\) занимают место \(3\)), можно получить хэш турнира, равный \(7020100\) (при \(A = 100\)). Однако такое распределение мест не может быть результатом турнира, потому что команды \(1\) и \(2\) обязательно должны играть друг с другом в полуфинале, поэтому они не могут занять два первых места.
F. Красно-чёрное число meet-in-the-middle дп математика поиск в глубину и подобное реализация *2100 Дано целое неотрицательное число \(x\), десятичная запись которого содержит \(n\) цифр. Необходимо покрасить каждую его цифру в красный или чёрный цвет, так чтобы число, образуемое красными цифрами, делилось на \(A\), а число, образуемое чёрными цифрами, делилось на \(B\). Как в красный, так и в чёрный цвет должна быть покрашена хотя бы одна цифра. Из всех таких покрасок числа \(x\), которые возможны, необходимо вывести любую такую, чтобы, если в красный покрашено \(r\) цифр, а в чёрный — \(b\) цифр, величина \(\|r - b\|\) была минимально возможной. Обратите внимание, что число \(x\), а также числа, образуемые цифрами одного цвета, могут содержать ведущие нули. $\text{[math]}$ Пример покраски числа для \(A = 3\) и \(B = 13\) На рисунке выше показан пример покраски числа \(x = 02165\) из \(n = 5\) цифр для \(A = 3\) и \(B = 13\). Красные цифры образуют число \(015\), которое делится на \(3\), а чёрные — \(26\), которое делится на \(13\). Заметим, что абсолютная величина разности количеств красных и чёрных цифр равна \(1\), меньшего значения добиться невозможно. Входные данные В первой строке записано одно целое число \(t\) (\(1 \le t \le 10\)) — количество наборов входных данных. Далее следуют \(t\) наборов входных данных. Каждый набор входных данных состоит из двух строк. Первая строка содержит три целых числа \(n\), \(A\), \(B\) (\(2 \le n \le 40\), \(1 \le A, B \le 40\)). Вторая строка содержит целое неотрицательное число \(x\), состоящее ровно из \(n\) цифр и, возможно, содержащее ведущие нули. Выходные данные Для каждого набора входных данных выведите в отдельной строке: -1, если не существует искомой покраски; строку \(s\) из \(n\) символов, каждый из которых является буквой «R» или «B». Если \(i\)-я цифра числа \(x\) красится в красный цвет, то \(i\)-й символ строки \(s\) должен быть буквой «R», иначе буквой «B». Число, которое образовано покрашенными в красный цвет цифрами, должно делится на \(A\). Число, которое образовано покрашенными в черный цвет цифрами, должно делится на \(B\). Значение \(\|r-b\|\) должно быть минимальным, где \(r\) — количество красных цифр, а \(b\) — количество чёрных. Если ответов несколько, то выведите любой из них. Примечание Первый набор входных данных разобран в условии. Во втором наборе входных данных нет чётных цифр, поэтому невозможно составить число, которое делится на \(2\). В третьем наборе входных данных любая покраска, содержащая хотя бы одну красную и одну чёрную цифру, подходит, поэтому можно покрасить \(4\) цифры в красный и \(4\) в чёрный (\(\|4 - 4\| = 0\), т. е. нельзя улучшить результат). В четвёртом наборе входных данных существует единственная искомая покраска.
F. Две сортировки meet-in-the-middle Бинарный поиск математика поиск в глубину и подобное *3400 Целые числа от \(1\) до \(n\) отсортировали по возрастанию в лексикографическом порядке, рассматривая их как строки, и получили массив \(a_1, a_2, \dots, a_n\). Требуется найти сумму \((\sum_{i = 1}^n ((i - a_i) \mod 998244353)) \mod 10^9 + 7\). \(x \mod y\) означает остаток от деления числа \(x\) на число \(y\) — этот остаток всегда неотрицателен и не превосходит \(y - 1\), например \(5 \mod 3 = 2\), \((-1) \mod 6 = 5\). Входные данные В первой строке содержится одно целое число \(n\) (\(1 \leq n \leq 10^{12}\)). Выходные данные Выведите одно целое число — ответ на задачу. Примечание Строка \(a\) лексикографически меньше строки \(b\), если и только если выполняется один из следующих пунктов: \(a\) — префикс \(b\), но \(a \ne b\); в первой позиции, где \(a\) и \(b\) различны, в строке \(a\) находится буква, которая встречается в алфавите раньше, чем соответствующая буква в \(b\). Например, \(42\) меньше \(6\) лексикографически, так как числа отличаются в первой позиции и \(4 < 6\); \(42 < 420\), так как \(42\) является префиксом \(420\). Обозначим \(998244353\) за \(M\). В первом примере последовательность \(a\) будет равна \([1, 2, 3]\). \((1 - 1) \mod M = 0 \mod M = 0\) \((2 - 2) \mod M = 0 \mod M = 0\) \((3 - 3) \mod M = 0 \mod M = 0\) В результате \((0 + 0 + 0) \mod 10^9 + 7 = 0\) Во втором примере последовательность \(a\) будет равна \([1, 10, 11, 12, 2, 3, 4, 5, 6, 7, 8, 9]\). \((1 - 1) \mod M = 0 \mod M = 0\) \((2 - 10) \mod M = (-8) \mod M = 998244345\) \((3 - 11) \mod M = (-8) \mod M = 998244345\) \((4 - 12) \mod M = (-8) \mod M = 998244345\) \((5 - 2) \mod M = 3 \mod M = 3\) \((6 - 3) \mod M = 3 \mod M = 3\) \((7 - 4) \mod M = 3 \mod M = 3\) \((8 - 5) \mod M = 3 \mod M = 3\) \((9 - 6) \mod M = 3 \mod M = 3\) \((10 - 7) \mod M = 3 \mod M = 3\) \((11 - 8) \mod M = 3 \mod M = 3\) \((12 - 9) \mod M = 3 \mod M = 3\) В результате \((0 + 998244345 + 998244345 + 998244345 + 3 + 3 + 3 + 3 + 3 + 3 + 3 + 3) \mod 10^9 + 7\) \(=\) \(2994733059 \mod 10^9 + 7\) \(=\) \(994733045\)
F. Интересные отрезки meet-in-the-middle разделяй и властвуй Структуры данных *2800 $\text{[math]}$ У Василия есть массив неотрицательных чисел \(a_1, a_2, \dots, a_n\). Он хочет, чтобы вы помогли ему узнать количество отрезков \(l \le r\), которые проходят проверку. Проверка отрезка выполняется следующим образом: Находится минимум и максимум среди чисел на отрезке массива от \(l\) до \(r\). Проверка считается пройденной, если в битовой записи минимума и максимума одинаковое количество единичных бит. Входные данные Первая строка содержит одно число \(n\) (\(1 \le n \le 10^6\)) — размер массива \(a\). Вторая строка содержит \(n\) целых чисел \(a_1, a_2, \dots, a_n\) (\(0 \le a_i \le 10^{18}\)) — описание массива \(a\). Выходные данные Выведите одно число — количество отрезков, прошедших проверку.
G. Длинная бинарная строка meet-in-the-middle битмаски математика матрицы теория чисел *2900 У вас есть бинарная строка \(t\) длины \(10^{100}\), и изначально все биты в строке равны \(\texttt{0}\). Вам также дана бинарная строка \(s\), и вы можете выполнять следующую операцию: Выберите некоторую подстроку \(t\) и замените ее на побитовое исключающее ИЛИ этой подстроки со строкой \(s\).\(^\dagger\) После некоторого количества операций в строке \(t\) ровно два бита должны быть равны \(\texttt{1}\); иными словами, должны существовать ровно два различных индекса \(p\) и \(q\) такие, что \(p\)-й и \(q\)-й биты строки \(t\) равны \(\texttt{1}\), а остальные биты равны \(\texttt{0}\). Найдите лексикографически максимальную \(^\ddagger\) строку \(t\), которая может получиться при выполнении этого условия, или определите, что таких строк получиться не может. \(^\dagger\) Формально, выберите индекс \(i\) такой, что \(0 \leq i \leq 10^{100}-\|s\|\). Для всех \(1 \leq j \leq \|s\|\), если \(s_j = \texttt{1}\), измените значение \(t_{i+j}\). То есть если \(t_{i+j}=\texttt{0}\), положите \(t_{i+j}=\texttt{1}\). Иначе, если \(t_{i+j}=\texttt{1}\), положите \(t_{i+j}=\texttt{0}\). \(^\ddagger\) Бинарная строка \(a\) лексикографически больше бинарной строки \(b\) такой же длины, если в первой позиции, где \(a\) и \(b\) различаются, строка \(a\) содержит \(\texttt{1}\), а строка \(b\) — \(\texttt{0}\). Входные данные Единственная строка содержит бинарную строку \(s\) (\(1 \leq \|s\| \leq 35\)). Выходные данные Если нельзя получить подходящую под условие строку \(t\), выведите -1. Иначе выведите два целых числа \(p\) и \(q\) (\(1 \leq p < q \leq 10^{100}\)) такие, что в лексикографически максимальной \(t\) \(p\)-й и \(q\)-й биты равны \(\texttt{1}\). Примечание В первом примере можно выполнить следующие операции. \(\)\texttt{00000}\ldots \to \color{red}{\texttt{1}}\texttt{0000}\ldots \to \texttt{1}\color{red}{\texttt{1}}\texttt{000}\ldots\(\) Во втором примере можно выполнить следующие операции. \(\)\texttt{00000}\ldots \to \color{red}{\texttt{001}}\texttt{00}\ldots \to \texttt{0}\color{red}{\texttt{011}}\texttt{0}\ldots\(\) В третьем примере можно выполнить следующие операции. \(\)\texttt{00000}\ldots \to \color{red}{\texttt{1111}}\texttt{0}\ldots \to \texttt{1}\color{red}{\texttt{0001}}\ldots\(\) Можно показать, что показанные выше строки \(t\) лексикографически максимальны. В четвертом примере нельзя сделать ни один бит равным \(\texttt{1}\), поэтому задача невыполнима.
F. Мультимножество строк meet-in-the-middle битмаски бпф графы Деревья дп математика Перебор Потоки *2500 Вам даны три целых числа \(n\), \(k\) и \(f\). Рассмотрим все бинарные строки (то есть все строки, состоящие из символов \(0\) и/или \(1\)) длины от \(1\) до \(n\). Для каждой такой строки \(s\) вы должны выбрать целое число \(c_s\) от \(0\) до \(k\). Мультимножество из бинарных строк длины ровно \(n\) считается красивым, если для каждой бинарной строки \(s\) длины от \(1\) до \(n\) выполняется следующее: количество строк в мультимножестве, для которых \(s\) является префиксом, не превосходит \(c_s\). Например, пусть \(n = 2\), \(c_{0} = 3\), \(c_{00} = 1\), \(c_{01} = 2\), \(c_{1} = 1\), \(c_{10} = 2\) и \(c_{11} = 3\). Мультимножество строк \(\{11, 01, 00, 01\}\) является красивым, так как: для строки \(0\) существует \(3\) строки из мультимножества, для которых \(0\) — префикс, и \(3 \le c_0\); для строки \(00\) существует одна строка из мультимножества, для которой \(00\) — префикс, и \(1 \le c_{00}\); для строки \(01\) существует \(2\) строки из мультимножества, для которых \(01\) — префикс, и \(2 \le c_{01}\); для строки \(1\) существует одна строка из мультимножества, для которой \(1\) — префикс, и \(1 \le c_1\); для строки \(10\) существует \(0\) строк из мультимножества, для которых \(10\) — префикс, и \(0 \le c_{10}\); для строки \(11\) существует одна строка из мультимножества, для которой \(11\) — префикс, и \(1 \le c_{11}\). А теперь — сама задача. Вы должны посчитать количество способов выбрать числа \(c_s\) для всех бинарных строк \(s\) длины от \(1\) до \(n\) таким образом, чтобы максимальный возможный размер красивого мультимножества был равен ровно \(f\). Входные данные В единственной строке заданы три целых числа \(n\), \(k\) и \(f\) (\(1 \le n \le 15\); \(1 \le k, f \le 2 \cdot 10^5\)). Выходные данные Выведите одно целое число — количество способов выбрать числа \(c_s\) для всех бинарных строк \(s\) длины от \(1\) до \(n\) таким образом, чтобы максимальный возможный размер красивого мультимножества был равен ровно \(f\). Так как ответ может быть очень большим, выведите его по модулю \(998244353\). Примечание В первом примере есть три способа выбрать значения \(c_s\): \(c_0 = 0\), \(c_1 = 2\), тогда максимальное красивое мультимножество — \(\{1, 1\}\); \(c_0 = 1\), \(c_1 = 1\), тогда максимальное красивое мультимножество — \(\{0, 1\}\); \(c_0 = 2\), \(c_1 = 0\), тогда максимальное красивое мультимножество — \(\{0, 0\}\).
E. Algebra Flash meet-in-the-middle битмаски графы Деревья дп математика Перебор *2500 Выпущена новая версия: Algebra Flash 2.2 Список изменений: Новый игровой режим! Благодарим вас за непрерывную поддержку игры! И это все? С небольшим разочарованием вы запускаете игру и нажимаете на новый режим. Написано «Цветные платформы». В ряд расположены \(n\) платформ, пронумерованных от \(1\) до \(n\). В игре доступны \(m\) цветов, пронумерованных от \(1\) до \(m\). \(i\)-я платформа раскрашена в цвет \(c_i\). Вы начинаете на платформе \(1\) и хотите добраться до платформы \(n\). За один ход вы можете прыгнуть с некоторой платформы \(i\) на платформы \(i + 1\) или \(i + 2\). Все платформы изначально деактивированы (включая платформы \(1\) и \(n\)). Для каждого цвета \(j\) можно заплатить \(x_j\) монет, чтобы активировать все платформы этого цвета. Вы хотите включить некоторые платформы так, чтобы можно было начать на активированной платформе \(1\), попрыгать по некотором активированным платформам и достичь платформы \(n\). Какое наименьшее количество монет потребуется для достижения этого? Входные данные В первой строке записаны два целых числа \(n\) и \(m\) (\(2 \le n \le 3 \cdot 10^5\); \(1 \le m \le 40\)) — количество платформ и количество цветов, соответственно. Во второй строке записаны \(n\) целых чисел \(c_1, c_2, \dots, c_n\) (\(1 \le c_i \le m\)) — цвета платформ. В третьей строке записаны \(m\) целых чисел \(x_1, x_2, \dots, x_m\) (\(1 \le x_i \le 10^7\)) — стоимости включения всех платформ каждого цвета. Выходные данные Выведите наименьшее количество монет, которое потребуется того, чтобы можно было начать на активированной платформе \(1\), попрыгать по некотором активированным платформам и достичь платформы \(n\).
H. Олимпийский тимбилдинг meet-in-the-middle Перебор *3500 Гвозден и Вукашин участвует в шахматной олимпиаде и хочет устроить тимбилдинг. Он собрал \(n\) игроков, где \(n\) является степенью \(2\), и предложил заняться спортом. Гвозден и Вукашин входит в число этих \(n\) человек. Одно из спортивных мероприятий — перетягивание каната. Для каждого \(1\leq i \leq n\) сила \(i\)-го игрока равна \(s_i\). Гвозден будет проводить раунды на выбывание до тех пор, пока не останется один игрок. Мы назовем этого игрока абсолютным победителем. В каждом раунде: Предположим, что \(m>1\) игроков все еще в игре, где \(m\) является степенью \(2\). Эти \(m\) игроков разбиваются на две команды равных размеров (т. е. по \(m/2\) в каждой команде). Сила команды равна сумме сил всех игроков. Если команды имеют равные значения силы, то Гвозден выбирает, кто выигрывает; иначе выигрывает более сильная команда. Все игроки в проигравшей команде выбывают, и остается \(m/2\) игроков. Гвозден может выбирать, как образуются команды на в каждом раунде, и команду-победителя в случае равных сил. Гвозден знает силу каждого игрока и ему интересно, кто может стать абсолютным победителем, а кто не может. Ответьте на этот вопрос. Входные данные Первая строка содержит одно целое число \(n\) (\(4 \leq n \leq 32\)) — количество игроков. Гарантируется, что \(n\) являются степенью \(2\). Вторая строка содержит последовательность целых чисел \(s_1,s_2, \ldots, s_n\) (\(1 \leq s_i \leq 10^{15}\)) — силы игроков. Выходные данные В единственной строке выведите бинарную строку \(s\) длины \(n\): \(i\)-й символ \(s\) должен быть равен \(1\), если \(i\)-й игрок может стать абсолютным победителем, и \(0\) в противном случае. Примечание В первом примере игроки \(1\) и \(4\), имеющие силы \(60\) и \(87\), могут стать абсолютными победителями. Опишем процесс для игрока \(1\). Изначально мы разделим игроков на команды \([1,3]\) и \([2,4]\). Силы команд равны \(60+59=119\) и \(32+87=119\). Так как они равны, то Гвозден может выбрать, кто выбывает, пусть это будет вторая команда. Остаются два игрока \(1\) и \(3\). Так как у \(1\) сила больше (\(60>59\)), то он побеждает и становится абсолютным победителем. В третьем примере силы остающихся игроков может быть \([8,8,8,8,4,4,4,4] \rightarrow [8,8,4,4] \rightarrow [8,4] \rightarrow [8]\). Любой игрок с силой \(8\) может стать абсолютным победителем, и можно показать, что все остальные не могут.
F. Даша и кошмары meet-in-the-middle битмаски Строки хэши *1900 Отличница Даша учится в лучшем математическом лицее страны. Недавно таинственный незнакомец принёс в лицей \(n\) слов из маленьких латинских букв \(s_1, s_2, \ldots, s_n\). С того дня Дашу начали мучить кошмары. Рассмотрим некоторую пару целых чисел \(\langle i, j \rangle\) (\(1 \le i \le j \le n\)). Кошмаром называется строка, для которой верно: Она получена склеиванием \(s_{i}s_{j}\); Её длина нечётна; Количество различных букв, входящих в неё, ровно \(25\); Количество каждой отдельной буквы, входящей в неё, нечётно. Например, если \(s_i=\) «abcdefg» и \(s_j=\) «ijklmnopqrstuvwxyz», пара \(\langle i, j \rangle\) образует кошмар. Даша знает, что кошмары исчезнут, если их посчитать. Кошмаров слишком много, поэтому Даше нужна ваша помощь. Посчитайте количество различных кошмаров. Кошмары считаются различными, если различны соответствующие им пары \(\langle i, j \rangle\). Пары \(\langle i_1, j_1 \rangle\) и \(\langle i_2, j_2 \rangle\) считаются различными, если \(i_1 \neq i_2\) или \(j_1 \neq j_2\). Входные данные В первой строке дано единственное целое число \(n\) (\(1 \le n \le 2 \cdot 10^5\)) — количество слов. В следующих \(n\) строках записаны слова \(s_1, s_2, \ldots, s_n\), состоящие из маленьких латинских букв. Гарантируется, что суммарная длина слов не превосходит \(5 \cdot 10^6\). Выходные данные Выведите единственное целое число — количество различных кошмаров. Примечание В первом тесте кошмары образуются парами \(\langle 1, 3 \rangle\), \(\langle 2, 5 \rangle\), \(\langle 3, 4 \rangle\), \(\langle 6, 7 \rangle\), \(\langle 9, 10 \rangle\).
F. Ещё одна n-мерная шоколадка meet-in-the-middle дп математика теория чисел *2700 Мама купила мальчику Васе \(n\)-мерную шоколадку, представляющую собой \(n\)-мерный куб, у которого длина каждой стороны равна \(1\). У шоколадки намечено разделение на дольки. По \(i\)-му измерению ее можно разделить гиперплоскостями на \(a_i\) равных частей. Таким образом, шоколадка делится суммарно на \(a_1 \cdot a_2 \cdot a_3 \cdot \ldots \cdot a_n\) долек, у каждой дольки длина по \(i\)-му измерению равна \(\frac{1}{a_i}\), соответственно объём каждой дольки равен \(\frac{1}{a_1 a_2 \cdots a_n}\). Вася с друзьями хочет разрезать шоколадку, чтобы получилось хотя бы \(k\) кусочков, при этом Вася хочет максимизировать объем наименьшего из них. Резать шоколадку можно только по местам соединения долек, причём каждый разрез должен проходить через всю шоколадку вдоль некоторой гиперплоскости, участвующей в образовании долек. Только сделав все разрезы, Вася разбирает шоколадку на кусочки. Более формально, Вася хочет выбрать числа \(b_1, b_2, \dots, b_n\) (\(1 \le b_i \le a_i\)) — количество частей на которые Вася разрежет шоколадку вдоль каждого измерения. Должно выполняться условие \(b_1 \cdot b_2 \cdot \ldots \cdot b_n \ge k\), чтобы получить не менее \(k\) кусочков после всех разрезаний. Можно заметить, что при оптимальном разрезании с такими параметрами, минимальный кусочек будет содержать \(\lfloor \frac{a_1}{b_1} \rfloor \dotsm \lfloor \frac{a_n}{b_n} \rfloor\) долек, а его объём будет равен \(\lfloor \frac{a_1}{b_1} \rfloor \dotsm \lfloor \frac{a_n}{b_n} \rfloor \cdot \frac{1}{a_1 a_2 \cdots a_n}\). Вася хочет получить максимальное возможное значение объема минимального кусочка, умноженного на \(k\), то есть он хочет максимизировать число \(\lfloor \frac{a_1}{b_1} \rfloor \dotsm \lfloor \frac{a_n}{b_n} \rfloor \cdot \frac{1}{a_1 a_2 \cdots a_n} \cdot k\). Помогите ему в этом. Входные данные В первой строке даны два целых числа \(n\) и \(k\) \((1 \le n \le 100\), \(1 \le k \le 10^7)\) — размерность шоколадки, и на сколько частей её нужно поделить. Во второй строке даны \(n\) целых чисел \(a_1,\ a_2,\ \dots,\ a_n\) \((1 \le a_i \le 10^7)\) — количество кусочков, на которое размечена шоколадка вдоль каждого из измерений. Выходные данные Выведите одно число — максимальный возможный объём наименьшего из полученных кусочков, умноженный на \(k\), с абсолютной или относительной погрешностью не более \(10^{-9}\). Если при заданных ограничениях разрезать шоколадку хотя бы на \(k\) кусочков невозможно, выведите \(0\). Примечание В первом примере одномерную шоколадку можно разделить так: $\text{[math]}$ Тогда ответ будет \(\frac{2}{5} \cdot 2 = 0.8\) Во втором примере шоколадку можно разрезать следующим образом: $\text{[math]}$ Тогда ответ будет \(\frac{2}{5} \cdot \frac{3}{10} \cdot 6 = 0.72\) В третьем примере шоколадку можно разрезать следующим образом: $\text{[math]}$ Тогда ответ будет \(\frac{2}{4} \cdot \frac{1}{4} \cdot 7 = 0.875\)
G1. В поисках истины (простая версия) meet-in-the-middle интерактив Конструктив математика Теория вероятностей *2200 Единственное отличие между версиями — максимальное количество запросов. В этой версии вы можете сделать не более \(2023\) запросов. Это интерактивная задача. Вы играете в игру. Круг разделен на \(n\) секторов, секторы пронумерованы от \(1\) до \(n\) в некотором порядке. Вы находитесь в соседней комнате и не знаете ни количество секторов, ни порядка их нумерации. Также есть стрелка, которая изначально указывает на какой-то сектор. Изначально ведущий сообщает вам номер сектора, на который указывает стрелка. После этого вы можете попросить ведущего переместить стрелку на \(k\) секторов по часовой стрелке или против часовой стрелки не более чем \(2023\) раза. И каждый раз вам сообщается номер сектора, на который указывает стрелка. Ваша задача определить число \(n\) — количество секторов, используя не более чем \(2023\) запроса. Гарантируется, что \(1 \le n \le 10^6\). Входные данные Входные данные состоят из одного целого числа \(x\) (\(1 \le x \le n\)) — номер начального сектора. Выходные данные После того, как вы определите число \(n\) — количество секторов, выведите «! n» (\(1 \le n \le 10^6\)). После этого программа должна немедленно завершиться. Обратите внимание, что вывод ответа не считается запросом. Гарантируется, что число \(n\) и номера секторов зафиксированы изначально и не будут меняться программой жюри в зависимости от запросов. Протокол взаимодействия После описания ввода вы можете задавать запросы. Запросы могут быть двух типов: «+ k» (\(0 \le k \le 10^9\)) — попросить переместить стрелку на \(k\) секторов по часовой стрелке. «- k» (\(0 \le k \le 10^9\)) — попросить переместить стрелку на \(k\) секторов против часовой стрелки. После каждого запроса вы должны считать целое число \(x\) (\(1 \le x \le n\)) — номер текущего сектора, на который указывает стрелка. Всего вы можете сделать не более \(2023\) запросов. Если вы сделаете слишком много запросов, вы получите вердикт Wrong answer. После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте: fflush(stdout) или cout.flush() в C++; System.out.flush() в Java; flush(output) в Pascal; stdout.flush() в Python; смотрите документацию для других языков. Примечание Взломы Для взломов используйте следующий формат теста. В первой строке выведите одно целое число \(n\) (\(1 \le n \le 10^6\)) — количество секторов. Во второй строке выведите \(n\) различных целых чисел \(1 \le a_1, a_2, \dots, a_n \le n\) — номера секторов по часовой стрелке, стрелка изначально указывает на сектор с номером \(a_1\).
G2. В поисках истины (сложная версия) meet-in-the-middle интерактив Конструктив математика Теория вероятностей *2500 Единственное отличие между версиями — максимальное количество запросов. В этой версии вы можете сделать не более \(1000\) запросов. Это интерактивная задача. Вы играете в игру. Круг разделен на \(n\) секторов, секторы пронумерованы от \(1\) до \(n\) в некотором порядке. Вы находитесь в соседней комнате и не знаете ни количество секторов, ни порядка их нумерации. Также есть стрелка, которая изначально указывает на какой-то сектор. Изначально ведущий сообщает вам номер сектора, на который указывает стрелка. После этого вы можете попросить ведущего переместить стрелку на \(k\) секторов по часовой стрелке или против часовой стрелки не более чем \(1000\) раз. И каждый раз вам сообщается номер сектора, на который указывает стрелка. Ваша задача определить число \(n\) — количество секторов, используя не более чем \(1000\) запросов. Гарантируется, что \(1 \le n \le 10^6\). Входные данные Входные данные состоят из одного целого числа \(x\) (\(1 \le x \le n\)) — номер начального сектора. Выходные данные После того, как вы определите число \(n\) — количество секторов, выведите «! n» (\(1 \le n \le 10^6\)). После этого программа должна немедленно завершиться. Обратите внимание, что вывод ответа не считается запросом. Гарантируется, что число \(n\) и номера секторов зафиксированы изначально и не будут меняться программой жюри в зависимости от запросов. Протокол взаимодействия После описания ввода вы можете задавать запросы. Запросы могут быть двух типов: «+ k» (\(0 \le k \le 10^9\)) — попросить переместить стрелку на \(k\) секторов по часовой стрелке. «- k» (\(0 \le k \le 10^9\)) — попросить переместить стрелку на \(k\) секторов против часовой стрелки. После каждого запроса вы должны считать целое число \(x\) (\(1 \le x \le n\)) — номер текущего сектора, на который указывает стрелка. Всего вы можете сделать не более \(1000\) запросов. Если вы сделаете слишком много запросов, вы получите вердикт Wrong answer. После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте: fflush(stdout) или cout.flush() в C++; System.out.flush() в Java; flush(output) в Pascal; stdout.flush() в Python; смотрите документацию для других языков. Примечание Взломы Для взломов используйте следующий формат теста. В первой строке выведите одно целое число \(n\) (\(1 \le n \le 10^6\)) — количество секторов. Во второй строке выведите \(n\) различных целых чисел \(1 \le a_1, a_2, \dots, a_n \le n\) — номера секторов по часовой стрелке, стрелка изначально указывает на сектор с номером \(a_1\).
I. Равные деревья особая задача meet-in-the-middle графы 3100 Задано два корневых дерева, состоящих из \(n\) вершин каждое. Вершины в деревьях пронумерованы от \(1\) до \(n\), корень дерева — вершина \(1\). Вы можете выполнять следующую операцию: выбрать дерево и вершину \(v\) (кроме корня дерева) в нем; соединить дочерние узлы \(v\) с родителем \(v\) и удалить \(v\) из дерева. Давайте скажем, что два дерева равны, если выполняются оба следующих условия: множества оставшихся вершин в обоих деревьях одинаковы; для каждой вершины \(v\), которая не удалена, ее родитель в первом дереве такой же, как и ее родитель во втором дереве. Ваша задача — вычислить минимальное количество вышеупомянутых операций, чтобы сделать деревья равными. Входные данные Первая строка содержит одно целое число \(n\) (\(2 \le n \le 40\)) — количество вершин в деревьях. Вторая строка содержит \(n-1\) целых чисел \(a_2, a_3, \dots, a_n\) (\(1 \le a_i \le n\)), где \(a_i\) — родитель \(i\)-й вершины в первом дереве. Вершина \(1\) — корень дерева. Третья строка содержит \(n-1\) целых чисел \(b_2, b_3, \dots, b_n\) (\(1 \le b_i \le n\)), где \(b_i\) — родитель \(i\)-й вершины во втором дереве. Вершина \(1\) — корень дерева. Выходные данные Выведите одно целое число — минимальное количество вышеупомянутых операций, чтобы сделать деревья равными.
E. Количество k-хороших подотрезков meet-in-the-middle битмаски дп Комбинаторика математика Перебор разделяй и властвуй *2300 Обозначим за \(bit(x)\) количество единичных бит в двоичной записи неотрицательного целого числа \(x\). Назовем подотрезок массива \(k\)-хорошим, если он состоит только из чисел, в которых не более \(k\) единичных бит, то есть подотрезок \((l, r)\) массива \(a\) хороший, если для любого \(i\), такого, что \(l \le i \le r\) выполняется \(bit(a_{i}) \le k\). У вас есть массив \(a\) длины \(n\), состоящий из последовательных неотрицательных целых чисел начиная с \(0\), то есть \(a_{i} = i\) для \(0 \le i \le n - 1\) (в \(0\)-индексации). Вам необходимо посчитать количество \(k\)-хороших подотрезков в этом массиве. Поскольку ответ может быть очень большим, выведите его по модулю \(10^{9} + 7\). Входные данные Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит целое число \(t\) (\(1 \le t \le 10^{4}\)) — количество наборов входных данных. Далее следует описание наборов входных данных. Единственная строка каждого набора входных данных содержит два целых числа \(n\), \(k\) (\(1 \le n \le 10^{18}, 1 \le k \le 60\)). Выходные данные Для каждого набора входных данных в отдельной строке выведите одно целое число — количество \(k\)-хороших подотрезков по модулю \(10^{9} + 7\). Примечание Для первого набора входных данных \(a = [0, 1, 2, 3, 4, 5]\), \(k = 1\). Чтобы найти ответ, давайте запишем все числа в двоичной записи: \(\)a = [\color{green}{000}, \color{green}{001}, \color{green}{010}, \color{red}{011}, \color{green}{100}, \color{red}{101}]\(\) Отсюда видно, что числа \(3\) и \(5\) имеют \(2 \ge (k = 1)\) единичных бита в двоичной записи, поэтому в ответ должны войти все подотрезки, в которых нет ни \(3\), ни \(5\), это отрезки (в \(0\)-индексации): (\(0\), \(0\)), (\(0\), \(1\)), (\(0\), \(2\)), (\(1\), \(1\)), (\(1\), \(2\)), (\(2\), \(2\)), (\(4\), \(4\)).
G. Оптимизация решетки meet-in-the-middle битмаски Перебор хэши *3400 Рассмотрим граф на сетке, состоящей из \(n\) строк и \(n\) столбцов. Пусть ячейка в строке \(x\) и столбце \(y\) будет обозначена как \((x,y)\). Существует направленное ребро из \((x,y)\) в \((x+1,y)\) с неотрицательным целым значением \(d_{x,y}\) для всех \(1\le x < n, 1\le y \le n\), а также существует направленное ребро из \((x,y)\) в \((x,y+1)\) с неотрицательным целым значением \(r_{x,y}\), для всех \(1\le x \le n, 1\le y < n\). Изначально вы находитесь в точке \((1,1)\) с пустым множеством \(S\). Вам нужно пройтись по ребрам и в конце концов достичь \((n,n)\). Каждый раз, когда вы проходите ребро, его значение будет добавляться в \(S\). Найдите максимальный MEX\(^{\text{∗}}\) множества \(S\), который можно получить, достигнув точки \((n,n)\). \(^{\text{∗}}\)Минимальное исключенное число (MEX) массива — это наименьшее неотрицательное целое число, которое не принадлежит массиву. Например: MEX массива \([2,2,1]\) равен \(0\), потому что \(0\) не принадлежит массиву. MEX массива \([3,1,0,1]\) равен \(2\), потому что \(0\) и \(1\) принадлежат массиву, а \(2\) — нет. MEX массива \([0,3,1,2]\) равен \(4\), потому что \(0, 1, 2\) и \(3\) принадлежат массиву, а \(4\) — нет. Входные данные Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число \(t\) (\(1\le t\le100\)) — количество наборов входных данных. Далее следует описание наборов входных данных. Первая строка каждого набора входных данных содержит одно целое число \(n\) (\(2\le n\le20\)) — количество строк и столбцов. Каждая из следующих \(n-1\) строк содержит \(n\) целых чисел, разделенных пробелами — матрица \(d\) (\(0\le d_{x,y}\le 2n-2\)). Каждая из следующих \(n\) строк содержит \(n-1\) целых чисел, разделенных пробелами — матрица \(r\) (\(0\le r_{x,y}\le 2n-2\)). Гарантируется, что сумма всех \(n^3\) не превосходит \(8000\). Выходные данные Для каждого набора входных данных выведите одно целое число — максимальное значение MEX для \(S\) при достижении \((n,n)\). Примечание В первом наборе входных данных граф решетки и один из оптимальных путей выглядят следующим образом: $\text{[math]}$ Во втором наборе входных данных граф сетки и один из оптимальных путей выглядят следующим образом: $\text{[math]}$
D. Сумма перестановок meet-in-the-middle битмаски дп Комбинаторика реализация 1900 Перестановкой p называется упорядоченный набор чисел p₁, p₂, ..., p_n, состоящий из n различных целых положительных чисел, каждое из которых не больше чем n. Обозначим i-ый элемент перестановки p через p_i. Число n будем называть размером или длиной перестановки p₁, p₂, ..., p_n. Петя решил ввести операцию суммы на множестве перестановок длины n. Пусть заданы две перестановки длины n: a₁, a₂, ..., a_n и b₁, b₂, ..., b_n. Суммой перестановок a и b Петя назвал такую перестановку c длины n, у которой c_i = ((a_i - 1 + b_i - 1) mod* n) + 1 (1 ≤ i ≤ n). Операция $\text{[math]}$ обозначает взятие остатка от деления числа x на число y. Очевидно, что не для всех перестановок a и b будет существовать перестановка c, являющаяся их суммой. Из-за этого Петя расстроился и попросил Вас для заданного n посчитать количество таких пар перестановок a и b длины n, что существует перестановка c, являющаяся суммой a и b. Пара перестановок x, y (x ≠ y) и пара перестановок y, x считаются различными парами. Так как ответ может получиться достаточно большим, выведите его остаток от деления на 1000000007 (10⁹ + 7). Входные данные В единственной строке находится целое число n (1 ≤ n ≤ 16). Выходные данные В единственной строке выведите целое неотрицательное число — количество таких пар перестановок a и b, что существует перестановка c, которая является суммой a и b, по модулю 1000000007 (10⁹ + 7).
E. Идем по оси meet-in-the-middle битмаски дп Комбинаторика Конструктив *2300 Яхуб хочет встретиться со своей подружкой Яхубиной. Они оба живут на оси Ox (горизонтальной оси координат). Яхуб живет в точке 0, а Яхубина живет в точке d. У Яхуба есть n целых положительных чисел a₁, a₂, ..., a_n. Сумма этих чисел равняется d. Предположим, что p₁, p₂, ..., p_n — это перестановка чисел {1, 2, ..., n}. Затем, пусть b₁ = a_p₁, b₂ = a_p₂ и так далее. Будем называть массив b — «путь». Существует n! различных путей, один путь для каждой перестановки p. Яхуб запланировал поход к своей подружке следующим образом. Сначала он проходит b₁ шагов по оси Ox, затем делает привал в точке b₁. Затем он проходит еще b₂ шагов по оси Ox и устраивает привал в точке b₁ + b₂. Аналогично, в j-ый раз (1 ≤ j ≤ n) он проходит еще b_j шагов по оси Ox и делает привал в точке b₁ + b₂ + ... + b_j. Яхуб очень суеверный человек. У него есть k несчастливых целых чисел. Яхуб называет путь «хорошим», если он никогда не делает привала в точке, соответствующей хотя бы одному из этих k чисел. Просто из любопытства посчитайте, сколько существует хороших путей по модулю 1000000007 (10⁹ + 7). Входные данные В первой строке записано целое число n (1 ≤ n ≤ 24). В следующей строке записано n целых чисел: a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹). В третьей строке записано целое число k (0 ≤ k ≤ 2). В четвертой строке записано k положительных целых чисел, обозначающих несчастливые для Яхуба числа. Каждое из этих чисел не превышает 10⁹. Выходные данные Выведите единственное целое число — ответ на дилемму Яхуба. Примечание В первом тесте посмотрим на шесть возможных путей: [2, 3, 5]. Яхуб остановится в точках 2, 5 и 10. Среди них несчастливое число — 5. [2, 5, 3]. Яхуб остановится в точках 2, 7 и 10. Среди них несчастливое число — 7. [3, 2, 5]. Остановка в несчастливой точке 5. [3, 5, 2]. Такое расположение подходит. [5, 2, 3]. Два несчастливых привала (5 и 7). [5, 3, 2]. Яхуб не согласится, так как здесь есть привал в точке 5. Во втором тесте заметьте, что два разных способа могут иметь идентичные наборы привалов. В конкретном случае, все шесть возможных способов имеют одни и те же остановки: [2, 4, 6], так что тут неудача не грозит Яхубу.
D. Даты событий meet-in-the-middle жадные алгоритмы сортировки *1900 На уроке истории учитель попросил Васю назвать даты, когда произошли n известных событий. Он не помнит точные даты, но для каждого события он помнит отрезок дней [l_i, r_i] (включительно), в которые оно могло произойти. Однако еще Вася помнит, что в один день могло произойти только одно событие. Помогите ему выбрать такие n дат известных событий, чтобы оба условия выполнялись. Гарантируется, что решение существует. Входные данные В первой строке записано целое число n (1 ≤ n ≤ 100) — количество известных событий. Далее следует n строк по два целых числа l_i и r_i в каждой (1 ≤ l_i ≤ r_i ≤ 10⁷) — самая ранняя допустимая дата и самая поздняя допустимая дата i-го события. Выходные данные Выведите n чисел — даты, в которые произошли события. Если решений несколько, выведите любое. Гарантируется, что решение существует.
A. Золотая система счисления meet-in-the-middle математика *1700 Piegirl надоела двоичная, десятичная и все остальные системы счисления с целочисленным основанием. Недавно она обнаружила весьма интересные свойства числа $\text{[math]}$ , одно из из них можно записать следующим образом: q² = q + 1. Piegirl считает, что число q может быть неплохим основанием для новой системы счисления, которую она назовет «золотая система счисления». Число в золотой системе счисления — это непустая строка, состоящая из нулей и единиц. Десятичное значение числа a₀a₁...a_n равно $\text{[math]}$ . Немного поизучав новую систему счисления, Piegirl поняла, что эта система не обладает некоторыми свойствами, которыми обладают системы счисления с целочисленным основанием. В частности, сравнение двух чисел в этой системе счисления — не такая тривиальная задача. Вам заданы два числа в золотой системе счисления, сравните их. Входные данные Входные данные состоят из двух строк, в каждой из которых записана непустая строка из нулей и единиц. Длина каждой строки не превосходит 100000. Выходные данные Выведите «>», если первое число больше второго; выведите «<», если первое число меньше второго; иначе, выведите «=». Примечание В первом примере первое число равно $\text{[math]}$ , второе число приблизительно равно 1.618033988² + 1.618033988 + 1 ≈ 5.236. Очевидно, что первое число меньше. Во втором примере числа равны. Каждое из них приблизительно равно ≈ 2.618.
E. Перманент meet-in-the-middle дп математика Паросочетания *3100 Little X на днях решил #P полную задачу за полиномиальное время. Теперь он задает эту задачу вам! Дана особая матрица A размера n × n, ваша задача — подсчитать ее перманент по модулю 1000000007 (10⁹ + 7). Особое свойство матрицы A заключается в том, что почти все ее элементы равняются 1. Только k элементов имеют заданное значение. Определение перманента можно найти по следующей ссылке: https://ru.wikipedia.org/wiki/Перманент Входные данные В первой строке записано два целых числа через пробел, n, k (1 ≤ n ≤ 10⁵; 1 ≤ k ≤ 50). В следующих k строках записано описание матрицы. В i-й строке записано три целых числа через пробел x_i, y_i, w_i (1 ≤ x_i, y_i ≤ n; 0 ≤ w_i ≤ 10⁹). Эти числа обозначают, что A_{x_i, y_i} = w_i. Все элементы матрицы, кроме заданных, равны 1. Гарантируется, что все позиции (x_i, y_i) различны. Выходные данные Выведите перманент матрицы по модулю 1000000007 (10⁹ + 7).
E. Волнистые числа meet-in-the-middle Перебор поиск в глубину и подобное сортировки *2900 Волнистым числом называется такое целое положительное число, что для каждой цифры десятичного представления, не являющейся первой или последней, она либо строго больше обеих соседних с ней цифр, либо строго меньше обеих соседних с ней цифр. Например, числа 35270, 102, 747, 20 и 3 являются волнистыми, а числа 123, 1000 и 2212 — нет. Для двух заданных целых чисел n и k требуется найти k-е по величине волнистое число r, которое делится нацело на n. Ваша задача — написать программу для нахождения искомого числа r в случае, если оно не превосходит 10¹⁴. Входные данные В единственной строке содержатся два целых числа n и k, разделенных одним пробелом (1 ≤ n, k ≤ 10¹⁴). Выходные данные Требуется вывести единственное целое число r — ответ на задачу. Если такого числа не существует или оно больше 10¹⁴, то требуется вывести «-1» (минус единицу без кавычек). Примечание Значения первых четырех волнистых чисел кратных n для первого примера входных данных: 492, 615, 738 и 1845.
D. Шоколадки meet-in-the-middle математика Перебор поиск в глубину и подобное теория чисел *1900 Поликарпу нравится делать подарки Прасковье. Вот и сейчас он купил две плитки шоколада, каждая из них имеет форму прямоугольника из долек. Первая плитка имеет размеры a₁ × b₁ долек, а вторая — a₂ × b₂ долек. Поликарп хочет угостить на большой перемене Прасковью одной плиткой, а вторую съесть сам. Кроме того, он хочет подчеркнуть одинаковую значимость ума Поликарпа и красоты Прасковьи, поэтому плитки должны содержать одинаковое количество долек. Чтобы сделать плитки равными по количеству долек, Поликарп каждую минуту съедает немного шоколада. Каждую минуту он: либо разламывает одну плитку ровно пополам (вертикально или горизонтально) и съедает ровно половину шоколадки, либо отламывает от плитки ровно одну треть (вертикально или горизонтально) и съедает ровно треть шоколадки. В первом случае от плитки останется половина, а во втором — две трети. Не всегда возможны оба развития событий, а иногда бывает, что Поликарп вообще не может отломить половину или треть. Например, если плитка имеет размер 16 × 23, то от нее можно отломить половину, но нельзя одну треть. Если плитка имеет размер 20 × 18, то от нее можно отломить как половину, так и треть. Если плитка имеет размер 5 × 7, то отломить как половину так и треть невозможно. Какое минимальное количество минут понадобится Поликарпу, чтобы сделать обе плитки одинаковыми по количеству долек в них? Найдите не только искомое минимальное количество минут, но и возможные размеры плиток после их вынужденного «уравнивания». Входные данные В первой строке входных данных записаны целые числа a₁, b₁ (1 ≤ a₁, b₁ ≤ 10⁹) — первоначальные размеры первой шоколадки. Во второй строке входных данных записаны целые числа a₂, b₂ (1 ≤ a₂, b₂ ≤ 10⁹) — первоначальные размеры второй шоколадки. Вы можете использовать типы данных int64 (в Паскале), long long (в С++), long (в Java) для работы с большими целыми числами (превосходящими 2³¹ - 1). Выходные данные В первую строку выведите m — искомое минимальное количество минут. Во вторую и третью строки выведите возможные размеры плиток после их уравнивания за m минут. Выводите размеры, используя формат, аналогичный формату входных данных. Размеры (числа в выводимых парах) выводите в любом порядке. Вторая строка должна соответствовать первой шоколадке, а третья — второй. Если решений несколько, выведите любое из них. Если решения не существует, то выведите единственную строку с числом -1.
G1. Инверсии meet-in-the-middle дп Перебор поиск в глубину и подобное *1800 Вам дана перестановка из n чисел p₁, p₂, ..., p_n. Мы совершаем k операций следующего типа: выбираем равновероятно случайным образом два индекса l и r (l ≤ r) и меняем порядок элементов p_l, p_l + 1, ..., p_r на обратный. Ваша задача — определить математическое ожидание количества инверсий в итоговой перестановке. Входные данные Первая строка входных данных содержит два целых числа n и k (1 ≤ n ≤ 100, 1 ≤ k ≤ 10⁹). Следующая строка содержит n целых чисел p₁, p₂, ..., p_n — данную перестановку. Все p_i различны и находятся в интервале от 1 до n. Задача состоит из трех подзадач, которые отличаются друг от друга ограничениями на входные данные. За решение каждой подзадачи вы получите определенное количество баллов. Описание подзадач следует ниже. В подзадаче G1 (3 балла) выполняется 1 ≤ n ≤ 6, 1 ≤ k ≤ 4. В подзадаче G2 (5 баллов) выполняется 1 ≤ n ≤ 30, 1 ≤ k ≤ 200. В подзадаче G3 (16 баллов) выполняется 1 ≤ n ≤ 100, 1 ≤ k ≤ 10⁹. Выходные данные Выведите ответ на задачу с абсолютной или относительной погрешностью не более чем 1e - 9. Примечание Рассмотрим первый пример. В перестановке (1, 2, 3) (которая изначально не содержит инверсий) будет выбран один интервал и порядок его элементов будет изменен на обратный. С вероятностью $\text{[math]}$ , интервал будет состоять из одного элемента и перестановка не изменится. С вероятностью $\text{[math]}$ мы поменяем местами первые два элемента и получим перестановку (2, 1, 3) с одной инверсией. С такой же вероятностью мы можем выбрать интервал, состоящий из последних двух элементов, что приведет к перестановке (1, 3, 2), в которой тоже одна инверсия. Наконец, с вероятностью $\text{[math]}$ выбранный случайным образом интервал будет содержать все элементы, что приведет к перестановке (3, 2, 1) с тремя инверсиями. Таким образом, мат.ожидание количества инверсий равно $\text{[math]}$ .
B. Drazil и его счастливые друзья meet-in-the-middle Перебор снм теория чисел *1300 У Drazil много друзей. Некоторые из них счастливы, а некоторые несчастны. Drazil хочет, чтобы все его друзья были счастливы. Поэтому он придумал такой план. Среди его друзей n юношей и m девушек. Пронумеруем их от 0 до n - 1 и 0 до m - 1 соответственно. В i-й день Drazil приглашает $\text{[math]}$ -го юношу и $\text{[math]}$ -ю девушку поужинать (Drazil программист, поэтому i принимает значения с нуля). Если один из этих двух людей счастлив, то и другой становится счастливым. В противном случае оба человека останутся в том состоянии, в котором они были изначально. Как только человек становится счастливым (или же если он был счастлив с самого начала), он остается счастливым навсегда. Drazil интересно, приведёт ли этот план к тому, что его друзья рано или поздно все станут счастливыми. Помогите ему найти ответ на этот вопрос. Входные данные В первой строке следуют два целых числа n и m (1 ≤ n, m ≤ 100). Во второй строке следует целое число b (0 ≤ b ≤ n), — количество счастливых парней среди друзей Drazil, затем следуют b различных целых чисел x₁, x₂, ..., x_b (0 ≤ x_i < n), — номера счастливых парней. В третьей строке следует целое число g (0 ≤ g ≤ m), — количество счастливых девушек среди друзей Drazil, затем следуют g различных целых чисел y₁, y₂, ... , y_g (0 ≤ y_j < m), — номера счастливых девушек. Гарантируется, что у Drazil есть не менее одного несчастного друга. Выходные данные Если Drazil может осчастливить всех своих друзей, воспользовавшись этим планом, выведите "Yes". В противном случае выведите "No". Примечание Определим $\text{[math]}$ как остаток от целочисленного деления i на k. В первом тесте из условия: В 0-й день Drazil приглашает 0-го парня и 0-ю девушку. Так как 0-я девушка изначально счастливая, 0-й юноша становится счастлив в этот день. В 1-й день Drazil приглашает 1-го парня и 1-ю девушку. Они оба несчастны, так что в этот день ничего не меняется. Во 2-й день Drazil приглашает 0-го парня и 2-ю девушку. Так как 0-й парень уже счастлив, в этот день он делает 2-ю девушку счастливой. В 3-й день Drazil приглашает 1-го парня и 0-ю девушку. 0-я девушка счастливая, она делает счастливым 1-го парня. В 4-й день Drazil приглашает 0-го парня и 1-ю девушку. 0-ой парень счастлив, так что он делает 1-ю девушку счастливой. Итак, в этот момент все друзья Drazil становятся счастливыми.
E. Аня и кубики meet-in-the-middle Бинарный поиск битмаски дп математика Перебор *2100 Аня очень любит складывать и наклеивать. Сегодня она решила заняться именно этим. У Ани есть n кубиков, лежащих в ряд и пронумерованных от 1 до n слева направо, с написанными на них натуральными числами. Также у нее есть k наклеек с восклицательными знаками. Известно, что количество наклеек не превышает количества кубиков. Аня может наклеить на кубик восклицательный знак и получить факториал числа, записанного на кубике. Например, если на кубике было написано 5, то после наклеивания будет 5!, что равно 120. Вам нужно помочь Ане посчитать, сколько существует способов оставить какое-то количество кубиков и наклеить на некоторые из них восклицательные знаки, использовав не более k восклицательных знаков, так, чтобы сумма чисел, написанных на кубиках (как отмеченных восклицательными знаками, так и нет), после наклеивания стала равна S. Аня может наклеить на один кубик не более одного восклицательного знака. Справитесь? Два способа будем считать одинаковыми, если совпадают номера оставленных кубиков, а также совпадают номера кубиков, на которые наклеены восклицательные знаки. Входные данные В первой строке входных данных заданы через пробел три целых числа n, k и S (1 ≤ n ≤ 25, 0 ≤ k ≤ n, 1 ≤ S ≤ 10¹⁶) — количество кубиков и количество наклеек, которые есть у Ани, и сумма, которую необходимо набрать. Во второй строке следуют n целых положительных чисел a_i (1 ≤ a_i ≤ 10⁹) — числа, записанные на кубиках. На разных кубиках могут быть написаны одинаковые числа. Выходные данные Выведите в первую строку выходных данных единственное целое неотрицательное число — количество способов оставить какое-то количество кубиков и наклеить на некоторые из них восклицательные знаки так, чтобы сумма чисел стала равна заданному числу S. Примечание В первом тесте из условия единственный способ достичь желаемого — оставить оба кубика, и наклеить на каждый из них по восклицательному знаку. Во втором тесте из условия единственный способ достичь желаемого — оставить оба кубика, но не клеить восклицательный знак ни на один из них. В третьем тесте из условия можно оставить любой из трёх кубиков, при этом на него можно как клеить, так и не клеить восклицательный знак, поэтому существует шесть способов достичь желаемого.
F. Упрощенный японский кроссворд meet-in-the-middle битмаски дп хэши 2400 В этой задаче вам предстоит написать программу, решающую упрощенный японский кроссворд для полей не более 5 × 20. Упрощенный японский кроссворд — это головоломка, в которой надо построить такое поле (каждая клетка либо белая, либо черная), которое соответствует заданной информации для строк и столбцов. Для каждой строки и каждого столбца задано количество блоков из черных клеток. Ваша задача — построить такое поле, для которого все эти количества имеют место быть. Например, если размеры поля n = 3, m = 5, а количества блоков для строк это [2, 3, 2], а для столбцов — [1, 0, 1, 2, 1], то решение может выглядеть так: $\text{[math]}$ Гарантируется, что для каждого теста, на котором будет запущена ваша программа, хотя бы одно решение головоломки существует. Входные данные В первой строке входных данных записаны два целых числа n, m (1 ≤ n ≤ 5, 1 ≤ m ≤ 20) — количество строк и столбцов соответственно. Вторая строка содержит n целых чисел a₁, a₂, ..., a_n, где a_i — количество черных блоков в i-й строке искомого поля. Аналогично, третья строка содержит m целых чисел b₁, b₂, ..., b_m, где b_i — количество черных блоков в i-м столбце искомого поля. Гарантируется, что хотя бы одно решение головоломки существует. Выходные данные Выведите любое из возможных решений. Ваш вывод должен содержать n строк по m символов в каждой из них. Белую ячейку следует обозначать символом «.», а черную — символом «».
C. Ваня и весы meet-in-the-middle дп жадные алгоритмы математика Перебор теория чисел *1900 У Вани есть чашечные весы и гири массами w⁰, w¹, w², ..., w¹⁰⁰ грамм, где w — некоторое целое число не меньше 2 (ровно по одной гире каждого номинала). Ваня хочет узнать, может ли он взвесить вещь с массой m с помощью данных гирь, если гири можно класть на обе чаши весов. Формально говоря, требуется определить, можно ли положить вещь массой m и некоторые гири на левую чашу весов, а некоторые гири на правую чашу весов таким образом, чтобы чаши весов были уравновешены. Входные данные В первой строке содержатся два целых числа w, m (2 ≤ w ≤ 10⁹, 1 ≤ m ≤ 10⁹) — число, задающее массы гирь и массу вещи. Выходные данные Выведите слово 'YES', если вещь можно взвесить и 'NO', если нельзя. Примечание Пояснение к первому тесту из условия. На одной чаше может быть вещь массой 7 и гиря массой 3, а на второй чаше две гири массами 9 и 1 соответственно. Тогда 7 + 3 = 9 + 1. Пояснение ко второму тесту из условия. На одной чаше может быть вещь массой 99 и гиря массой 1, а на второй гиря массой 100. Пояснение к третьему тесту из условия. Взвесить вещь, как описано в условии, невозможно.
D. Lizard Era: Beginning meet-in-the-middle *2300 В игре Lizard Era: Beginning главному герою предстоит путешествие с тремя спутницами: Линн, Мелианой и Ворриган. Всего в игре n обязательных заданий, для выполнения каждого из них нужно взять ровно двух спутниц. Отношение каждой из спутниц к герою характеризуется целым числом. Изначально отношение каждой из них к герою нейтрально и равно 0. В процессе выполнения задания главный герой совершает поступки, которые изменяют отношение к нему спутниц, которых он взял на выполнение этого задания, в положительную или отрицательную сторону (а могут и не менять вовсе). Сообщите, каких спутниц нужно выбирать главному герою, чтобы после выполнения всех заданий значения их отношения к герою были равны между собой. Если это можно сделать несколькими способами, выберите тот, в котором эти значения наибольшие. Входные данные В первой строке содержится целое положительное число n (1 ≤ n ≤ 25) — количество заданий, обязательных для выполнения. Следующие n строк содержат описание заданий — i-я строка содержит три числа l_i, m_i, w_i — величины, на которые изменятся отношения к главному герою Линн, Мелианы или Ворриган соответственно, в случае, если герой возьмет их с собой на выполнение i-го задания. Все числа во входных данных целые и не превышают по абсолютному значению 10⁷. Выходные данные В случае, если решения не существует, в первой строке выведите "Impossible". В противном случае выведите n строк, в каждой из них по два символа — в i-й строке выводите первые буквы имен спутниц, которых герой должен взять с собой на выполнение i-ого задания ('L' — Линн, 'M' — Мелиана, 'W' — Ворриган). Буквы выводите в любом порядке. Если решений несколько, выведите любое.
F. Медведи и сок meet-in-the-middle дп математика *2900 В гостинице поселились n медведей, но там есть только p спальных мест. Медведи планируют закатить большую вечеринку на несколько ночей (и дней). Медведи любят пить сок. Они не любят вино, но не могут отличить его от сока ни по вкусу, ни по запаху. Медведь ложится спать, только если он выпил вина, при этом он уходит спать через несколько часов после этого. Он проснётся только спустя много дней, когда вечеринка уже будет окончена. Хозяин гостиницы Радевуш хочет предложить медведям несколько бочек с напитками. При этом ровно одна бочка будет содержать вино, а в остальных будет содержаться сок. После этого Радевуш предложит медведям определить, в какой бочке находится вино. Каждую ночь происходит следующее (ровно в таком порядке): Каждый медведь выбирает какой-то (возможно, пустой) набор бочек. Одна и та же бочка может быть выбрана несколькими медведями. Каждый медведь выпивает по одному стакану из каждой бочки, которую он выбрал. Все медведи, пившие вино, отправляются спать (то есть те медведи, у которых в множестве выбранных бочек была бочка с вином). Они просыпаются спустя много дней, когда вся вечеринка уже окончена. Если свободных спальных мест недостаточно, то медведи автоматически проигрывают. В конце вечеринки, если однозначно можно определить, в какой бочке находится вино, и хотя бы один медведь не спит, то медведи выигрывают (если, конечно, они не проиграли раньше, потому что кому-то не хватило спальных мест). Радевуш хотел бы, чтобы медведи выиграли. Он рассматривает q сценариев игры. В i-м сценарии вечеринка продолжается i ночей. Далее пусть R_i обозначает максимальное количество бочек, для которого медведи точно смогут выиграть, если будут действовать оптимально. Обозначим $\text{[math]}$ . Вам требуется вычислить $\text{[math]}$ , где $\text{[math]}$ означает побитовое исключающее или (также известное как XOR). Обратите внимание, что одна и та же бочка может быть выбрана несколькими медведями и все они одновременно пойдут спать, если она содержит вино. Входные данные В единственной строке входных данных записаны три целых числа n, p и q (1 ≤ n ≤ 10⁹, 1 ≤ p ≤ 130, 1 ≤ q ≤ 2 000 000) — количество медведей, количество спальных мест и количество сценариев соответственно. Выходные данные Выведите единственное целое число, равное $\text{[math]}$ . Примечание В первом примере в гостинице находятся 5 медведей и есть только 1 спальное место. Имеем R₁ = 6, R₂ = 11, R₃ = 16, так что ответ равен $\text{[math]}$ . Проанализируем стратегию для сценария с 2 днями. Всего есть R₂ = 11 бочек, и 10 из них содержат сок. В первую ночь i-й медведь выбирает бочку i. Если одна из 5 бочек содержит вино, то соответствующий медведь отправится спать. Таким образом, медведи выигрывают, потому они теперь знают где находится вино и есть хотя бы один не спящий медведь. Если никто из 5 медведей не ушёл спать, то на вторую ночь i-й медведь пьёт из бочки 5 + i. Если хотя бы одна из бочек 6 – 10 содержит вино, то соответствующий медведь отправится спать, и медведи победят. Если никто из медведей опять не уйдёт спать, то они точно будут знать, что вино находится в бочке 11. Во втором примере есть только один медведь. Он не может ничего пить (то есть он выбирает пустое множество бочек каждую ночь), потому что если он уйдёт спать, то медведи сразу проигрывают. Таким образом, для любого числа дней R_i = 1 и ответ равен $\text{[math]}$ .
G. МАТЕМАТNКА meet-in-the-middle дп математика Перебор теория чисел *3200 Если вы дошли до этой задачи, вы всё равно вряд ли станете читать легенду... Вам дана бинарная строка $\text{[math]}$ и целое число $\text{[math]}$ . Найдите количество целых k, 0 ≤ k < N, таких что для всех i = 0, 1, ..., m - 1 $\text{[math]}$ Выведите ответ по модулю 10⁹ + 7. Входные данные В первой строке входного файла содержится строка s, состоящая из символов 0 и 1 (1 ≤ \|s\| ≤ 40). В следующей строке содержится целое число n (1 ≤ n ≤ 5·10⁵). В каждой из следующих n строк содержатся два разделённых пробелом целых числа p_i, α_i (1 ≤ p_i, α_i ≤ 10⁹, p_i простое). Все p_i различны. Выходные данные Едиственное число — ответ на задачу.
D. k-Интересные пары чисел особая задача meet-in-the-middle битмаски Перебор 1700 У Васи есть последовательность, состоящая из n целых чисел. Вася считает пару чисел x и y k-интересной, если их двоичное представление отличается друг от друга ровно в k битах. Например, если k = 2, то пара чисел x = 5 и y = 3 является k-интересной, так как двоичные представления x=101 и y=011 отличаются ровно в двух битах. Васе стало интересно, сколько в его последовательности существует пар индексов (i, j) таких, что i < j и пара чисел a_i и a_j является k-интересной. Перед вами стоит задача помочь Васе и определить это количество. Входные данные В первой строке следует два целых числа n и k (2 ≤ n ≤ 10⁵, 0 ≤ k ≤ 14) — количество чисел в последовательности Васи и количество битов, в которых должны отличаться числа в k-интересной паре. Во второй строке следует последовательность a₁, a₂, ..., a_n (0 ≤ a_i ≤ 10⁴), которая есть у Васи. Выходные данные Выведите количество пар (i, j) таких, что i < j и пара чисел a_i и a_j является k-интересной. Примечание В первом примере существует 4 k-интересные пары: (1, 3), (1, 4), (2, 3), (2, 4). Во втором примере k = 0. Следовательно, числа в любой k-интересной паре должны быть равны между собой. Таким образом, для второго примера существует 6 k-интересных пар: (1, 5), (1, 6), (2, 3), (2, 4), (3, 4), (5, 6).
D. Расширение поля meet-in-the-middle дп Перебор *2100 Одна из игр, которыми увлекается Аркадий, происходит на прямоугольном участке. В процессе игры Аркадий может покупать расширения для своего участка, каждое расширение в несколько раз увеличивает любую из двух сторон его участка. Формально, есть n расширений, i-е из них позволяет увеличить длину или ширину (по выбору Аркадия) участка в a_i раз. Каждое расширение можно использовать не более одного раза, расширения можно использовать в любом порядке. Сейчас участок Аркадия имеет размер h × w. Он хочет его расширить так, чтобы возможно было разместить на участке прямоугольное поле размером a × b (вдоль или поперек, параллельно сторонам участка). Найдите минимальное число расширений, которое будет достаточно Аркадию для достижения своей цели. Входные данные В первой строке следуют пять целых чисел a, b, h, w и n (1 ≤ a, b, h, w, n ≤ 100 000) — размеры поля, которое нужно разместить на участке, размеры участка, а также количество доступных расширений. Во второй строке следует последовательность n целых чисел a₁, a₂, ..., a_n (2 ≤ a_i ≤ 100 000), где a_i равно количеству раз, в которое может быть увеличена сторона при применении к ней i-го расширений. Выходные данные Выведите минимальное число расширений, которое будет достаточно Аркадию для достижения своей цели. Если невозможно поместить поле на участок после использования всех расширений, выведите -1. Если поле изначально помещается на участок, выведите 0. Примечание В первом примере достаточно использовать любое из доступных расширений. Например, можно увеличить h в 5 раз, использовав второе расширение. Тогда h станет равно 10 и станет возможно поместить поле на получившийся расширенный участок.
E. Мать драконов meet-in-the-middle графы математика Перебор *2700 В Королевстве Ланнистеров n замков и несколько стен, соединяющих два замка, никакие два замка не соединены более, чем одной стеной, ни одна стена не соединяет замок с собой. Сир Джейме Ланнистер узнал, что Дейенерис Таргариен собирается атаковать его королевство. Он хочет защитить свои владения. У него есть k литров странной жидости. Он хочет распределить эту жидкость между замками так, чтобы каждый замок содержал некоторое количество жидкости (возможно, нулевое или нецелое количество литров). После этого стабильность стены, соединяющей замки a и b, содержащие x и y литров жидкости, соответственно, равна x·y. Ваша задача — найти максимальную возможную сумму стабильностей стен, которую Сир Джейме Ланнистер сможет достичь Входные данные Первая строка содержит два целых числа n и k (1 ≤ n ≤ 40, 1 ≤ k ≤ 1000). Далее следует n строк. В i-й из них содержится n целых чисел a_i, 1, a_i, 2, ..., a_i, n ( $\text{[math]}$ ). Если замки i и j соединены стеной, a_i, j = 1. В противном случае оно равно 0. Гарантируется, что a_i, j = a_j, i и a_i, i = 0 для всех 1 ≤ i, j ≤ n. Выходные данные Выведите одно число — максимальную возможную сумму стабильностей стен, которую Сир Джейме Ланнистер сможет достичь. Ваш ответ будет считаться правильным, если его абсолютная или относительная точность не превосходит 10^- 6. А именно, если ваш ответ равен a, а ответ жюри равен b, то ваш ответ будет зачтен, если $\text{[math]}$ . Примечание В первом примере, если замки 1, 2, 3 содержат 0.5, 0.5, 0 литров жидкости, соответственно, ответ равен 0.25. Во втором примере, если замки 1, 2, 3, 4 содержат 1.0, 1.0, 1.0, 1.0 литров жидкости, ответ равен 4.0.
F. Яичная рулетка meet-in-the-middle битмаски математика Перебор разделяй и властвуй *3300 В Яичную рулетку играют два игрока. Изначально 2R сырых яйца и 2C вареных яйца кладутся в коробку в случайном порядке. Яйца все еще в скорлупе, поэтому невозможно отличить сырое яйцо от вареного. По одному игроки выбирают одно яйцо и разбивают его о свой лоб. Если яйцо было вареное, ничего особенного не произойдет, но если оно было сырое, то оно все испачкает. Такое продолжается до тех пор, пока один из игроков не разобьет R сырых яиц. В этот момент игра заканчивается, этот игрок объявляется проигравшим, а его соперник — победителем. Порядок, в котором ходят игроки, может быть представлен как строка из букв «A» и «B», где i-й символ обозначает игрока, который будет выбирать i-е яйцо. Традиционно игроки ходят по очереди, то есть, они следуют порядку «ABABAB...». Это не очень честно, так как второй игрок будет выигрывать чаще, чем первый. Мы хотим, чтобы вы нашли более честный порядок ходов. Определим нечестность порядка как модуль разности между вероятностью победы первого игрока и вероятностью победы второго игрока. Нам интересны порядки, в которых нечестность является минимально возможной. Мы считаем порядок корректным, если в нем одинаковое количество букв «A» и «B». Вам будет дана строка S длины 2(R + C), содержащая только символы «A», «B» и «?». Порядок подходит под S, если он отличается от S только в позициях, где S содержит «?». Среди корректных порядков, минимизирующих нечестность, сколько подходят под S? Входные данные Первая строка содержит целые числа R и C (1 ≤ R, C ≤ 20, R + C ≤ 30). Вторая строка содержит строку S, имеющею длину 2(R + C) и состоящую только из символов «A», «B», «?». Выходные данные Выведите количество корректных порядков, которые минимизируют нечестность и подходят под S. Примечание В первом тесте из примере минимальная нечестность равна 0, а порядки, минимизирующие ее, это «ABBA» и «BAAB», но ни один из них не подходит под S. Заметьте, что порядок «ABBB» также имеет нечестность 0, но он не является корректным, так как не содержит одинаковое число «A» и «B». Во втором примере единственно подходящим порядком является «BBAAABABABBA».
E. Максимальная подпоследовательность meet-in-the-middle битмаски разделяй и властвуй *1800 Вам дан массив a, состоящий из n целых чисел и целое число m. Выберите последовательность позиций b₁, b₂, ..., b_k (1 ≤ b₁ < b₂ < ... < b_k ≤ n) такую, чтобы значение $\text{[math]}$ было максимально. Выбранная подследовательность может быть пустой. Подсчитайте максимальное возможное значение $\text{[math]}$ . Входные данные В первой строке записаны два целых числа n и m (1 ≤ n ≤ 35, 1 ≤ m ≤ 10⁹). Во второй строке записаны n целых чисел a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹). Выходные данные Выведите максимальное возможное значение $\text{[math]}$ . Примечание В первом примере можно выбрать последовательность b = {1, 2}, чтобы сумма $\text{[math]}$ была равна 7 (равна 3 по модулю 4). Во втором примере можете выбрать последовательность b = {3}.
E. Простой подарок meet-in-the-middle Бинарный поиск математика поиск в глубину и подобное теория чисел *2400 — Мужик, у тебя простые числа есть? — Нету. — На, мужик, простые числа. Пингвин В отличие от Гриши, который вел себя хорошо, Олег за весь год так и не научился решать задачи на теорию чисел. Поэтому вместо Деда Мороза к нему пришел его сокомандник Андрей и торжественно вручил ему множество из n различных простых чисел вместе с простой задачей: Олегу необходимо найти k-е в порядке возрастания положительное целое число, среди простых делителей которого встречаются числа только из этого множества. Входные данные В первой строке задано целое число n (1 ≤ n ≤ 16) — количество чисел во множестве. Во второй строке n различных простых чисел p₁, p₂, ..., p_n (2 ≤ p_i ≤ 100) — числа во множестве. Гарантируется, что числа идут в порядке возрастания. В третьей строке задано число k (1 ≤ k). Гарантируется, что k-е в порядке возрастания положительное целое число, среди простых делителей которого встречаются числа только из данного множества не превосходит 10¹⁸. Выходные данные Выведите k-е в порядке возрастания число, удовлетворяющее условию. Гарантируется, что оно не превосходит 10¹⁸. Примечание Для первого примера последовательность с простыми делителями из набора {2, 3, 5} выглядит так: (1, 2, 3, 4, 5, 6, 8, ...) Седьмым по счету числом (в 1-индексации) как раз и будет восьмерка.
E. Number Clicker meet-in-the-middle графы разделяй и властвуй теория чисел *2700 Аллен играет в Number Clicker на телефоне. Он начинает с целого числа \(u\) на экране. Каждую секунду он нажимает одну из трех кнопок: Изменить \(u \to u+1 \pmod{p}\). Изменить \(u \to u+p-1 \pmod{p}\). Изменить \(u \to u^{p-2} \pmod{p}\). Аллен хочет нажать на кнопки не более 200 раз так, чтобы получить на экране число \(v\). Помогите ему! Входные данные Первая строка содержит три целых числа: \(u, v, p\) (\(0 \le u, v \le p-1\), \(3 \le p \le 10^9 + 9\)). Гарантируется, что \(p\) — простое. Выходные данные В первой строке выведите одно целое число \(\ell\) — количество нажатий кнопок. Во второй строке выведите целые числа \(c_1, \dots, c_\ell\) — кнопки, которые должен нажать Аллен. Для всех \(1 \le i \le \ell\) должно выполняться \(1 \le c_i \le 3\). Можно показать, что ответ всегда существует. Примечание В первом примере число на экране меняется следующим образом: \(1 \to 2 \to 3\). Во втором примере число на экране меняется следующим образом: \(3 \to 2\).
Robot Instructions meet-in-the-middle Беси учится управлять роботом, который она недавно получила в подарок. Робот начинает в точке \((0, 0)\) координатной плоскости и Беси хочет привести робота в точку \((x_g, y_g)\). Изначально у Беси есть список из \(N\) (\(1\le N\le 40\)) инструкций для робота, \(i\)-ая из которых перемещает робота на \(x_i\) единиц вправо и на \(y_i\) единиц вверх (или влево и вниз, если \(x_i\) и \(y_i\) отрицательные, соответственно). Для каждого \(K\) от \(1\) to \(N\), вычислите количество способов, которыми Беси может выбрать \(K\) инструкций из исходного списка так, что после применения этих \(K\) инструкций, робот окажется в точке \((x_g, y_g)\). Замечание: лимиты на время и память в этой задаче увеличены вдвое до 4s и 512MB, относительно значений по умолчанию. ФОРМАТ ВВОДА (с клавиатуры / stdin): Первая строка содержит \(N\). Следующая строка содержит \(x_g\) и \(y_g\), каждое в интервале \(-10^9 \ldots 10^9\). Последующие \(N\) описывают инструкции. Каждая строка содержит два целых числа \(x_i\) и \(y_i\), также в интервале \(-10^9 \ldots 10^9\). Гарантируется, что \((x_g,y_g)\neq (0,0)\) и \((x_i,y_i)\neq (0,0)\) для всех \(i\). ФОРМАТ ВЫВОДА (на экран / stdout): Выведите \(N\) строк, количество способов, которыми Беси может выбрать \(K\) инструкций из списка оригинальных \(N\), для каждого \(K\) от \(1\) до \(N\).
Balanced Cow Subsets meet-in-the-middle У Фермера Джона есть N cows (2 <= N <= 20), и корова I производит M(i) единиц молока ежедневно (1 <= M(i) <= 100,000,000). ФД хочет рационализировать процесс ежедневной дойки коров, поэтому он установил новый доильный аппарат в амбаре. Есть одно НО – аппарат работает, только если коровы на левой стороне амбара имеют такое же общее количество молока, как и коровы на правой стороне амбара. Назовем подмножество коров «сбалансированным», если оно может быть разбито на две группы, имеющие равные суммарные надои молока. ФД хочет, чтобы Вы посчитали, сколько подмножеств из его N коров сбалансированы. PROBLEM NAME: subsets Формат входных данных * Строка 1: Целое N. * Строки 2..1+N: Строка i+1 содержит M(i). Формат выходных данных * Строка 1: Количество сбалансированных подмножеств коров. Примечание Подмножество {1,2,3} может быть разбито на {1,2} и {3}. Подмножество {1,3,4} может быть разбито на {1,3} и {4}. Подмножество {1,2,3,4} может быть разбито на {1,4} и {2,3}.
Красивые разбиения meet-in-the-middle битмаски Напомним, что простое число — это целое число, которое делится ровно на два целых числа: на единицу и на себя. Последовательность простых чисел начинается с \(2, 3, 5, \ldots\). Рассмотрим первые \(n\) простых чисел. Давайте разделим их на две части \(A\) и \(B\) так, чтобы каждое простое число принадлежало ровно одной из этих двух частей. Обозначим произведение всех простых чисел в \(A\) как \(a\), а произведение всех простых чисел в \(B\) как \(b\). Произведение чисел в пустом множестве будем считать равным \(1\). Будем называть разбиение красивым, если \(a < b\) и \(b-a\) минимальное возможное. Дано \(n\), найдите красивое разбиение множества первых \(n\) простых чисел и выведите соответствующее значение \(a\). Формат входных данных Входные данные содержит целое число \(n\) на отдельной строке (\(1 \le n \le 30\)). Формат выходных данных Выведите значение \(a\) в красивом разбиении множества первых \(n\) простых чисел.

Олимпиадный тренинг

ФОРМАТ ВВОДА (с клавиатуры / stdin):

ФОРМАТ ВЫВОДА (на экран / stdout):