Биби вырос, наступила пора покинуть родительское гнездо и отправиться навстречу новым знаниям. Пин не хочет потерять с сыном связь, поэтому решил смастерить для него телеграф.
Чтобы научиться пользоваться телеграфом, Биби должен последовательно отправить с его помощью $$$n$$$ сообщений $$$s_1, s_2, \dots, s_n$$$.
Пин предусмотрел, что с большой вероятностью Биби захочет отправлять одинаковые сообщения, например «hello father», несколько раз, поэтому добавил кнопку «$$$\uparrow$$$», которая загружает в телеграф предыдущее отправленное сообщение.
Таким образом, Биби может отправить сообщение $$$s$$$ одним из двух способов:
- набрать сообщение посимвольно и нажать «Enter», выполнив суммарно $$$|s|+1$$$ ($$$|s|$$$ — это длина строки $$$s$$$) нажатие;
- если Биби уже отправлял такое же сообщение ранее, нажать на «$$$\uparrow$$$» произвольное количество раз $$$k$$$, загрузив в телеграф $$$k$$$-е по счёту с конца отправленное сообщение, и нажать «Enter», выполнив суммарно $$$k+1$$$ нажатие.
Помогите Биби последовательно отправить все сообщения, выполнив как можно меньшее суммарное число нажатий.
В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
В первой строке каждого набора дано целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество сообщений.
В следующих $$$n$$$ строках каждого набора дана последовательность сообщений $$$s_1, s_2, \ldots, s_n$$$, состоящих из строчных и заглавных букв латинского алфавита, а также пробелов. Сообщения разделены переводами строк.
Гарантируется, что сумма длин сообщений по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Также гарантируется, что первый и последний символы каждого сообщения не являются пробелами.
Для каждого набора входных данных выведите единственное целое число — минимальное количество нажатий, необходимое для отправки всех сообщений.
46hihihello fatheri am finehello fatherhi3abababa6kroshpinezikkrosh and ezikpingoodbye4hello kroshgoodbyehello ezikgoodbye
3494234
Во втором наборе входных данных оптимальна следующая последовательность действий: «a», «b», «a», «Enter», «b», «Enter», «$$$\uparrow$$$», «$$$\uparrow$$$», «Enter».
В третьем наборе входных данных одна из оптимальных последовательностей: «k», «r», «o», «s», «h», «Enter», «p», «i», «n», «Enter», «e», «z», «i», «k», «Enter», «k», «r», «o», «s», «h», « », «a», «n», «d», « », «e», «z», «i», «k», «Enter», «$$$\uparrow$$$», «$$$\uparrow$$$», «$$$\uparrow$$$», «Enter», «g», «o», «o», «d», «b», «y», «e», «Enter».
Обратите внимание, что сообщения могут содержать пробелы. Для считывания набора входных данных на языке C++ вы можете использовать представленный ниже сниппет.
#include <iostream>
#include <string>
using namespace std;
void solve() {
int n; cin » n;
string tmp; getline(cin, tmp);
for (int i = 0; i < n; ++i) {
string s; getline(cin, s);
// ...
}
}
Карыч забыл что-то очень важное и сильно обеспокоился из-за этого. Смешарики решили ему помочь.
Они подключили Карыча к компьютеру Лосяша и обнаружили $$$n$$$ воспоминаний $$$s_1, s_2, \ldots, s_n$$$, представленных в виде строк.
Карыч может переместиться из воспоминания $$$s_i$$$ в воспоминание $$$s_j$$$, если существует такой символ $$$c$$$, что $$$f(s_i, c) \gt 0$$$ и $$$f(s_i, c) = f(s_j, c)$$$, где $$$f(s, c)$$$ — количество вхождений символа $$$c$$$ в строку $$$s$$$. После такого перемещения компьютер Лосяша нагреется на $$$f(s_i, c)$$$ градусов. Если возможных перемещений несколько, Карыч может выбрать любое.
Расстоянием от воспоминания $$$s_i$$$ до воспоминания $$$s_j$$$ называется суммарный нагрев компьютера Лосяша на пути Карыча от $$$s_i$$$ к $$$s_j$$$.
Карыч забыл, какое из воспоминаний является важным. Помогите ему определить минимальное расстояние от первого воспоминания до всех остальных. Если до каких-то воспоминаний добраться невозможно, определите это.
В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
В первой строке каждого набора дано целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — количество воспоминаний.
В следующих $$$n$$$ строках даны воспоминания $$$s_1, s_2, \ldots, s_n$$$, состоящие из строчных букв латинского алфавита.
Гарантируется, что сумма длин $$$s_i$$$ по всем наборам входных данных не превосходит $$$10^6$$$.
Для каждого набора входных данных выведите $$$n - 1$$$ целых чисел — минимальные расстояния до воспоминаний $$$s_2, s_3, \ldots, s_n$$$ соответственно. Если какое-то воспоминание недостижимо, выведите вместо минимального расстояния «-1».
32ulyanovskisthebestmoscowisthebest2abcdefgh5ullllyyyyyyaaaaaaaannnnnnnnnnovsk
1-12 5 9 14
Нюша поссорилась с Барашем, объелась конфет и заскучала. У неё осталось бесконечное количество конфет каждого цвета. Цвет конфеты определяется целым числом от $$$1$$$ до $$$n$$$.
Чтобы развлечься, она выложила из конфет квадрат $$$n \times n$$$, оставив какие-то клетки пустыми. Каждый цвет встречается в квадрате $$$n$$$ раз или не встречается вообще.
Квадрат называется красивым, если цвета в каждой строке и каждом столбце образуют перестановку чисел от $$$1$$$ до $$$n$$$.
Помогите Нюше дополнить квадрат до красивого или сообщите, что это невозможно.
В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
В первой строке каждого набора дано целое число $$$n$$$ ($$$1 \le n \le 100$$$) — размер квадрата.
В следующих $$$n$$$ строках каждого набора даны $$$n$$$ целых чисел $$$a_{i,1}, a_{i,2}, \ldots, a_{i,n}$$$ ($$$0 \le a_{i,j} \le n$$$) — цвета конфет в $$$i$$$-й строке квадрата. Если $$$a_{i,j} = 0$$$, то конфета в соответствующей ячейке отсутствует.
Гарантируется, что каждый присутствующий в квадрате цвет встречается ровно $$$n$$$ раз.
Также гарантируется, что в каждой строке и в каждом столбце нет повторяющихся цветов.
Также гарантируется, что сумма $$$n^2$$$ по всем наборам входных данных не превосходит $$$10^4$$$.
Для каждого набора входных данных выведите в первой строке «YES», если Нюша сможет дополнить квадрат до красивого, и «NO» иначе.
При положительном ответе выведите $$$n$$$ строк, содержащих по $$$n$$$ чисел — вариант заполнения квадрата. Если ответов несколько, вы можете вывести любой.
331 2 32 3 13 1 21050 4 2 0 00 2 0 4 04 0 0 2 02 0 0 0 40 0 4 0 2
YES1 2 32 3 13 1 2YES1YES5 4 2 3 13 2 1 4 54 1 5 2 32 5 3 1 41 3 4 5 2
Это особая задача. Внимательно прочитайте примечание (замечание).
Совунья случайно нашла в старых вещах $$$n$$$ писем от своего ухажёра из прошлого. Её накрыли воспоминания о $$$n$$$ памятных датах, и в порыве чувства упущенного счастья она решила уничтожить все письма как можно скорее.
Каждое письмо соединяет ребром какие-то памятные даты $$$v$$$ и $$$u$$$. Каждую пару памятных дат соединяет не более одного письма.
Памятные даты $$$v$$$ и $$$u$$$ находятся в одной компоненте связности, если можно добраться из $$$v$$$ в $$$u$$$ по рёбрам. Известно, что изначально все памятные даты находятся в одной компоненте связности.
За одно действие Совунья может порвать не более половины писем в каждой компоненте связности. Половина округляется вверх до ближайшего целого.
Помогите Совунье порвать все письма за как можно меньшее количество действий.
В первой строке дано целое число $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — количество памятных дат и писем.
В следующих $$$n$$$ строках даны целые числа $$$v$$$, $$$u$$$ ($$$1 \le v, u \le n$$$, $$$v \neq u$$$) — описание писем.
Гарантируется, что все памятные даты находятся в одной компоненте связности.
В первой строке выведите целое число $$$k$$$ ($$$1 \le k \le 20$$$) — количество действий.
Далее выведите описание действий.
В первой строке $$$i$$$-й итерации выведите целое число $$$c_i$$$ ($$$1 \le c_i \le n$$$) — количество удалённых писем.
Во второй строке $$$i$$$-й итерации выведите $$$c_i$$$ целых чисел $$$d_1, d_2, \ldots, d_{c_i}$$$ ($$$1 \le d_j \le n$$$) — номера удалённых писем в порядке ввода.
51 23 45 12 33 5
4 2 1 4 1 2 1 5 1 3
В этой задаче всего один скрытый тест, сгенерированный случайно. Вы будете соревноваться на нём с другими участниками олимпиады. В разделе «Протокол» для каждой успешной посылки вы увидите количество операций, за которое справились. Для посылок со статусом «Неправильный ответ» вы увидите короткое сообщение чекера, которое может помочь при дебаге.
Во время тура ваше решение проверяется на корректность, но не на минимальность. Вы можете получить вердикт «Ожидает подтверждения». Он означает, что решение вывело корректную последовательность операций. Если вы сдадите корректное решение повторно, статус предыдущего решения поменяется на «Проигнорировано». К финальному тестированию на минимальность будет допущено ваше последнее корректное решение.
Финальное тестирование будет проведено после окончания тура. Участники, порвавшие все письма за минимальное количество действий среди всех участников, получат вердикт «ОК». Остальные участники, сдавшие корректное решение, получат вердикт «Неправильный ответ». Решение жюри не участвует в соревновании. Например, если корректное решение сдал всего один участник, он гарантированно получит вердикт «ОК», но если корректное решение сдали четыре участника, из них первые два справились за шесть действий, третий за семь, а четвёртый за двадцать, вердикт «ОК» получат только первые два.
Штраф считается по обычным правилам, как-будто посылка с вердиктом «Ожидает подтверждения» является посылкой с вердиктом «ОК», при этом посылки с вердиктом «Проигнорирована» игнорируются.
Это интерактивная задача.
Крош пришёл в очередной раз поиграть в компьютер Лосяша, но вместо привычных игр «Принц для Юши 2» или «Крутой спуск» он обнаружил новую игру «Коварные демонюги». Крошу очень понравилась эта игра, но он постоянно проигрывал. Помогите Крошу составить стратегию, с которой он будет выигрывать чаще, чем проигрывать.
В данной задаче вам будут предоставлены правила игры против интерактора в «Коварные демонюги». Чтобы решить эту задачу, вам нужно выиграть у интерактора хотя бы $$$500$$$ из $$$1000$$$ игр. Интерактор не является адаптивным, то есть не подстраивается под ваш стиль игры.
«Коварные демонюги» — карточная игра, в которой карты пронумерованы и выложены по кругу. В этой игре у каждой карты есть своя роль.
Представим роли:
- Рыцарь. Это персонаж, которого нельзя убить, если он не врёт.
- Охотник. Это персонаж, который скажет, на каком расстоянии от него находится Демон, но не скажет, в каком направлении. Если этот персонаж врёт, он скажет случайное число от $$$1$$$ до $$$\frac{n}{2}$$$ с округлением вниз.
- Гренадер. Если вы убьёте этого персонажа, когда он не врёт, игра заканчивается поражением.
- Шут. Персонаж, который позволяет выбрать три различные карты, и он скажет, сколько Демонов среди них. Способность Шута можно использовать только один раз за игру. Если будут выбраны не различные карты, игра закончится поражением.
- Судья. Персонаж, который позволяет выбрать одну карту и узнать, врёт ли она. Эту способность можно использовать только один раз за игру.
- Демон. Эта карта всегда врёт и будет притворяться другой ролью, а также заставляет соседние слева и справа карты врать. Когда карта врёт, Судья, Охотник и Шут предоставляют неправильную информацию; Рыцаря можно будет убить; Гренадер не закончит игру вашим поражением.
За один ход игрок может выполнить одно из трёх действий:
- Открыть неоткрытую карту. При этом игрок теряет $$$2$$$ жизни.
- Убить любую карту (открытую или закрытую):
- Если игрок пытается убить Демона, то игрок побеждает.
- Если игрок пытается убить Рыцаря, который врёт, то игрок теряет $$$5$$$ жизней.
- Если игрок пытается убить Рыцаря, который не врёт, то игрок не теряет жизней.
- Если игрок пытается убить Гренадера, который не врёт, то игрок проигрывает.
- Иначе игрок теряет $$$3$$$ жизни.
- Использовать способность открытой карты. За это действие жизни не тратятся.
В первой строке каждой игры вводится единственное число $$$n$$$ ($$$5 \le n \le 8$$$) — количество карт в игре.
В этой задаче четыре теста с разными $$$n$$$.
| Тест | Ограничения |
| 1 | $$$n = 5$$$ |
| 2 | $$$n = 6$$$ |
| 3 | $$$n = 7$$$ |
| 4 | $$$n = 8$$$ |
Интерактор не адаптивен, то есть не пытается подстроить состояние игры против вас. Состояние игры предрешено в начале игры и не меняется в зависимости от ваших действий.
Если в какой-то момент вы получили на вход слово «stop», это значит, что вы проиграли, и необходимо завершить программу. Например, у вас закончилось здоровье или вы сделали некорректный ход.
Вы можете использовать три команды:
- kill $$$x$$$ — вы убиваете карту под номером $$$x$$$ (считая с единицы).
- unc $$$x$$$ — вы переворачиваете карту под номером $$$x$$$, если она не была перевёрнута, иначе ваш ход заканчивается. После этого действия вы получаете $$$2$$$ урона.
- use $$$\text{pos}$$$ — вы используете способность Судьи или Шута на позиции $$$\text{pos}$$$, после этого вам предложат ввести одно или три числа для соответствующих ролей. Обратите внимание: если нужной роли на позиции $$$\text{pos}$$$ не существует или она ещё не открыта, то игра сразу закончится.
Если была использована команда kill, вы получите сообщение «win», если вы убили Демона и нужно перейти к следующей игре, или «miss $$$x$$$» ($$$x \lt 0$$$), если вы этого не сделали: вы получаете $$$|x|$$$ урона.
Если была использована команда unc, вы получите информацию о выбранной карте:
- 'K' — Рыцарь;
- 'H' — Охотник;
- 'S' — Гренадер;
- 'B' — Шут;
- 'J' — Судья.
Обратите внимание, что ни одна карта не вскроется сама как Демон.
Если вы получили на вход букву 'H', следом вы получите число x — расстояние, на котором находится Демон.
Если была использована команда use, вам нужно ввести одно или три числа для Судьи и Шута соответственно:
- Если была использована способность Шута, вернётся одно число — количество Демонов среди $$$3$$$ выбранных карт, число от $$$0$$$ до $$$3$$$.
- Если была использована способность Судьи, вернётся одно число — $$$0$$$, если карта врёт, $$$1$$$, если карта не врёт.
Не забывайте сбрасывать буфер после каждого вывода. Для этого можете использовать std::endl в C++ или стандартную функцию print в Python. Не используйте ios_base::sync_with_stdio(false) в C++.
5 miss -3 H 2 win ...
kill 2 unc 4 kill 1 ...
Что произошло в примере:
Первым действием мы убили карту на позиции $$$2$$$, это был не Демон и не Рыцарь.
Вторым действием мы открыли карту на позиции $$$4$$$, и это оказался Охотник, который сказал, что на расстоянии $$$2$$$ находится Демон.
Третьим действием мы убили Демона; оказалось, что Охотник не соврал.
Ёжик долго собирал свою коллекцию. В ней представлены $$$n$$$ фантиков, которые Крош оценил в $$$a_1, a_2, \ldots, a_n$$$ морковок.
Крош и Ёжик решили доказать свою дружбу, разделив все фантики из коллекции между собой честно. Разделение называется честным, если модуль разности суммарной стоимости фантиков Кроша и фантиков Ёжика не превосходит $$$100$$$.
Помогите друзьям разделить фантики честно.
В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
В первой строке каждого набора дано целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество фантиков.
Во второй строке каждого набора даны $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 100$$$) — стоимости фантиков в морковках.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите в первой строке целое число — модуль разности для честного разбиения.
В следующей строке выведите $$$n$$$ символов 'K' или 'E', обозначающих, что Крош или Ёжик взяли $$$i$$$-й фантик.
Можно показать, что при указанных ограничениях честное разделение всегда существует.
Если ответов несколько, вы можете вывести любой. Обратите внимание, что вам не требуется минимизировать модуль разности.
3112100 10056 27 61 14 15
1 E 0 KE 11 EKEKK
В третьем наборе входных данных Ёжик взял фантики стоимостью $$$6 + 61 = 67$$$ морковок, а Крош — стоимостью $$$27 + 14 + 15 = 56$$$ морковок. Модуль разности стоимостей $$$67 - 56 = 11$$$, $$$11 \le 100$$$, значит, разбиение является честным.
Страшные дела творятся в Ромашковой долине.
Железная няня активируется в точке $$$(0, 0)$$$ и начинает искать бодрствующих смешариков. Смешарики прячутся в каких-то точках и не меняют свою позицию.
Далее происходят $$$q$$$ событий, события бывают двух видов:
- Железная няня обнаруживает бодрствующего смешарика в точке $$$(x, y)$$$, при этом остаётся на месте;
- Железная няня перемещается в ближайшую точку с бодрствующим смешариком и укладывает его спать; если таких точек несколько, Железная няня перемещается в лексикографически минимальную.
Ближайшей к точке $$$(x_1, y_1)$$$ называется точка $$$(x_2, y_2)$$$, которая минимизирует величину $$$|x_1 - x_2| + |y_1 - y_2|$$$ (Манхэттенское расстояние).
Определите точки, в которых смешарики будут уложены спать.
В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
В первой строке каждого набора дано целое число $$$q$$$ ($$$1 \le q \le 10^5$$$) — количество событий.
В следующих $$$q$$$ строках каждого набора даны события:
- $$$1$$$ $$$x$$$ $$$y$$$ ($$$1 \le x, y \le 10^5$$$) — Железная няня обнаруживает нового бодрствующего смешарика;
- $$$2$$$ — Железная няня укладывает спать ближайшего бодрствующего смешарика.
Гарантируется, что сумма $$$q$$$ по всем наборам входных данных не превосходит $$$10^5$$$.
Также гарантируется, что в одном наборе входных данных в событиях первого типа все точки $$$(x, y)$$$ попарно различны.
Также гарантируется, что перед любым событием второго типа известно положение хотя бы одного бодрствующего смешарика.
Для каждого события второго типа выведите точку, в которую переместилась Железная няня.
191 1 21 2 121 4 11 3 221 2 422
1 22 13 24 1
Изначально няня находится в точке $$$(0,0)$$$.
Перед первым удалением бодрствующие смешарики находятся в точках $$$(1,2)$$$ и $$$(2,1)$$$. Они равноудалены от няни, поэтому выбирается лексикографически минимальная точка $$$(1,2)$$$.
Перед вторым удалением бодрствующие смешарики находятся в точках $$$(2,1)$$$, $$$(3,2)$$$ и $$$(4,1)$$$. Ближайшие точки — $$$(2,1)$$$ и $$$(3,2)$$$, поэтому выбирается $$$(2,1)$$$.
Перед третьим удалением бодрствующие смешарики находятся в точках $$$(2,4)$$$, $$$(3,2)$$$ и $$$(4,1)$$$. Выбирается $$$(3,2)$$$.
Перед четвёртым удалением бодрствующие смешарики находятся в точках $$$(2,4)$$$, $$$(4,1)$$$. Выбирается $$$(4,1)$$$.
Это задача с открытыми тестами.
Пин построил игровой аппарат, в котором можно выиграть морковку. Для обеспечения честности он зафиксировал несколько псевдослучайных булевых функций, определяющих результат игры. Функция под номером $$$t$$$ задаётся от $$$n_t$$$ булевых переменных. Игра должна быть непредсказуемой и честной, поэтому функций не должен знать никто, кроме Пина и вас.
Чтобы скрыть реализацию от игроков, Пин при постройке автомата использует только $$$\mathrm{nand}$$$-компоненты. Каждый такой компонент принимает два входных бита и возвращает один бит в соответствии с таблицей ниже.
| a | b | a nand b |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Две булевы функции $$$f_1$$$ и $$$f_2$$$ называются эквивалентными, если $$$$$$ f_1(x_1, \dots, x_{n_t}) = f_2(x_1, \dots, x_{n_t}) $$$$$$ для любых значений переменных $$$x_1, x_2, \dots, x_{n_t} \in \{0, 1\}$$$.
Для каждого теста по заданному номеру $$$t$$$ постройте схему из $$$\mathrm{nand}$$$-компонент, которая будет задавать функцию, эквивалентную указанной в таблице. Количество использованных $$$\mathrm{nand}$$$-компонент не должно превышать заданный лимит, потому что вместимость гаража Пина конечна.
| Номер | $$$n_t$$$ | Функция | Лимит nand-компонент |
| 0 | 3 | $$$(x_1 | x_2) \& x_3$$$ | 20 |
| 1 | 2 | $$$(x_1 | x_2)$$$ | 3 |
| 2 | 4 | $$$ x_4 \oplus ((x_1 | x_2 | x_4) \& x_3) $$$ | 15 |
| 3 | 5 | $$$ x_1 \oplus x_2 \oplus x_4 \oplus (x_1 \& x_3) \oplus (x_2 \& x_5) \oplus (x_3 \& x_4 \& x_5) \oplus 1 $$$ | 25 |
| 4 | 6 | $$$ ((x_1 | x_2 | x_3) \& (x_2 | x_3 | x_5 | x_6)) \oplus (x_1 \& x_4)$$$ | 21 |
| 5 | 6 | $$$ (\neg(x_1 \& x_2) | x_3) \oplus ((x_4 \& x_5 \& x_6) | (x_4 \oplus x_6))$$$ | 14 |
| 6 | 8 | $$$ (x_1 \oplus x_3) | ((x_2 \& x_5) \oplus x_6) | ((x_3 | x_4 | x_5 | x_6 | x_7 | x_8) \oplus (x_2 \& x_6)) $$$ | 33 |
В единственной строке дано целое число $$$t$$$ ($$$0 \le t \le 6$$$) — номер функции, для которой необходимо построить схему.
Для функции под номером $$$t$$$ выведите в первой строке целое число $$$m_t$$$ — количество используемых $$$\mathrm{nand}$$$-компонент. Оно не должно превышать соответствующий лимит для функции.
В следующих $$$m_t$$$ строках выведите описание $$$\mathrm{nand}$$$-компонент в формате «$$$x\_a$$$ nand $$$x\_b$$$». Входные переменные функции под номером $$$t$$$ заданы переменными $$$x\_1, x\_2, \ldots, x\_{n_t}$$$ и могут быть использованы в качестве входных битов для $$$\mathrm{nand}$$$-компонент.
Все $$$\mathrm{nand}$$$-компоненты исполняются последовательно. Результат выполнения каждого компонента записывается в переменную с минимальным неиспользованным номером. Результатом всех вычислений является результат выполнения последнего компонента.
0
5 x_1 nand x_1 x_2 nand x_2 x_4 nand x_5 x_6 nand x_3 x_7 nand x_7
Ниже представлены таблицы истинности для битовых операций, используемых в условии.
| a | b | a nand b | a $$$\&$$$ b | a | b | $$$\neg$$$ a | a $$$\oplus$$$ b |
| 0 | 0 | 1 | 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 | 0 | 0 |
Бараш наконец-то смог уединиться и тут же взялся за сочинение долгожданного стихотворения. Его новый стих содержит $$$2^n$$$ строк, в которых $$$a_1, a_2, a_3, \ldots, a_{2^n}$$$ слогов соответственно.
Поэты привыкли к одностишьям, двустишьям, четверостишьям и т.д., поэтому прекрасно работают со степенями двойки. Бараш построил над своим стихом полное бинарное дерево, записав в листья значения $$$a_1, a_2, \ldots, a_{2^n}$$$. Напомним, что полным бинарным деревом называется бинарное дерево, каждая вершина которого имеет 0 или 2 сына.
Согласно новой литературной теории Бараша, стих шедевральный, если все $$$a_i$$$ в полном бинарном дереве попарно различны. Эта гениальная идея пришла к нему довольно поздно, поэтому было проще дописать стих и потом немного подправить его, чем переписывать с нуля.
Бараш выбрал для себя действие, которым будет редактировать стих. Он рассматривает построенное дерево, удаляет одно из поддеревьев и на его место копирует любое другое поддерево (возможно, другого размера), заменив все $$$a_i$$$ из поддерева на $$$a_i \oplus k$$$. Для лучшего понимания ниже дана иллюстрация одного редактирования с $$$k=4$$$.
Бараш хочет как можно скорее прочитать шедевральный стих друзьям. Помогите ему найти минимальное число редактирований или сообщите, что сделать стих шедевральным невозможно.
В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
В первой строке каждого набора даны два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 20$$$, $$$0 \le k \le 2^{31} - 1$$$).
Во второй строке каждого набора даны $$$2^n$$$ целых чисел $$$a_1, a_2, \ldots, a_{2^n}$$$ ($$$0 \le a_i \le 2^{31} - 1$$$) — количества слогов.
Гарантируется, что сумма $$$2^{n}$$$ по всем наборам входных данных не превосходит $$$2^{20}$$$.
Для каждого набора входных данных выведите минимальное количество редактирований или $$$-1$$$, если получить шедевральный стих невозможно.
83 42 7 3 9 2 3 5 42 41 2 3 42 12 3 2 32 02 2 1 12 10 0 0 02 13 3 3 11 132 42 10 1 0 0
102-12102
Первый пример совпадает с картинкой из условия.
Рядом с домиком Лосяша был обнаружен неведомый цветок инопланетного происхождения.
Лосяш очень им заинтересовался. Если существование цветка не получится объяснить научным методом, то он будет уничтожен.
Довольно быстро Лосяш смог определить параметр цветка: число $$$n$$$.
Проведя множество бессонных ночей за исследованиями, он смог вывести критерий того, что существование цветка поддаётся научному объяснению. Оно поддаётся научному объяснению тогда и только тогда, когда существует такое целое положительное число $$$x$$$, что среди чисел $$$x, x + 1, \ldots, x + n - 1$$$ нет числа, взаимно простого со всеми остальными. Другими словами, должно существовать такое целое число $$$x$$$ ($$$1 \le x$$$), что не существует целого числа $$$i$$$ ($$$0 \le i \le n - 1$$$), такого, что для любого $$$j$$$ ($$$0 \le j \le n - 1$$$, $$$i \neq j$$$) $$$\gcd(x + i, x + j) = 1$$$.
Лосяшу известно, что число $$$x$$$ может быть очень большим, поэтому он хочет найти остатки от деления $$$x$$$ на все простые числа, не превосходящие $$$n$$$. Для публикации научной статьи этого будет достаточно.
Помогите Лосяшу найти $$$x$$$ и определить судьбу цветка.
В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 2500$$$) — количество наборов входных данных.
В единственной строке каждого набора дано целое число $$$n$$$ ($$$2 \le n \le 5000$$$) — параметр цветка.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$5000$$$.
Для каждого набора входных данных выведите «-1», если числа $$$x$$$ не существует.
В противном случае выведите в первой строке количество простых чисел, не превосходящих $$$n$$$. Во второй строке выведите остатки от деления $$$x$$$ на эти простые числа по порядку ($$$x \mod 2, x \mod 3, x \mod 5, \ldots$$$). Если ответов несколько, вы можете вывести любой.
2220
-180 2 0 5 0 10 0 0
Во втором примере подходит, например, число $$$x = 7745540$$$. Его остатки от деления на первые восемь простых чисел — это остатки в ответе.
Копатыч тайно готовится к вторжению марсиан.
Участок Копатыча представляет собой клетчатое поле из $$$n$$$ строк и $$$m$$$ столбцов. Копатыч заранее установил $$$2 k$$$ систем вентиляции в различных позициях $$$(x_1, y_1), (x_2, y_2), \ldots, (x_{2k}, y_{2k})$$$.
Для длительной обороны необходимо выкопать $$$k$$$ подкопов. Каждый подкоп должен соединять какую-то пару систем вентиляции. Каждая система вентиляции должна быть частью ровно одного подкопа. Чтобы система подкопов была отказоустойчивой, никакие два подкопа не должны пересекаться. Другими словами, каждая клетка участка может принадлежать не более чем одному подкопу.
Помогите Копатычу подготовить подкопы для обороны.
В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
В первой строке каждого набора даны целые числа $$$n$$$, $$$m$$$, $$$k$$$ ($$$1 \le n, m \le 500$$$, $$$2 \le \max(n, m)$$$, $$$1 \le k \le \frac{n \cdot m}{2}$$$) — количество строк, столбцов и подкопов.
В следующих $$$2 k$$$ строках каждого набора даны пары чисел $$$(x_1, y_1), (x_2, y_2), \ldots, (x_{2k}, y_{2k})$$$ ($$$1 \le x_i \le n$$$, $$$1 \le y_i \le m$$$) — позиции систем вентиляции.
Гарантируется, что сумма $$$n \cdot m$$$ по всем наборам входных данных не превосходит $$$250\,000$$$.
Для каждого набора входных данных выведите описания $$$k$$$ подкопов.
Описание каждого подкопа должно содержать в первой строке число $$$s_i$$$ — количество клеток участка в $$$i$$$-м подкопе.
Следующие $$$s_i$$$ строк должны содержать по два целых числа $$$x_i$$$, $$$y_i$$$ ($$$1 \le x_i \le n$$$, $$$1 \le y_i \le m$$$) — описание клеток подкопа. Первая и последняя клетки должны содержать системы вентиляции. Соседние клетки должны быть соседними по стороне.
3 3 3 2 1 1 1 3 3 1 3 3 3 5 3 3 3 1 1 1 3 1 4 2 5 2 1 4 4 1 4 1 1 4
3 1 1 1 2 1 3 3 3 1 3 2 3 3 2 1 1 2 1 2 1 3 1 4 4 3 3 3 4 3 5 2 5 7 4 1 3 1 2 1 1 1 1 2 1 3 1 4
В первом наборе входных данных мы можем соединить подкопом первую систему вентиляции со второй, подкопом с координатами $$$(1, 1)$$$, $$$(1, 2)$$$, $$$(1, 3)$$$, а третью систему вентиляции с четвертой подкопом с координатами $$$(3, 1)$$$, $$$(3, 2)$$$, $$$(3, 3)$$$ (см. картинку).
