Это задача с коммуникацией.
Есть два игрока: игрок A (Изабель) и игрок B (Тара). Сначала жюри взаимодействует с игроком A. После того как игрок A завершит взаимодействие, жюри начнёт взаимодействовать с игроком B. Обратите внимание, что игроки A и B не могут напрямую передавать друг другу информацию; оба игрока могут только отправлять информацию жюри или получать её от жюри, однако они могут заранее договориться о стратегии общения.
Изабель хочет передать Таре бинарную строку $$$b$$$ длины $$$n$$$. Для передачи информации она может использовать полное бинарное дерево ровно из $$$2^h-1$$$ вершин, где данное положительное целое число $$$h$$$ обозначает высоту дерева. Вершины пронумерованы целыми числами от $$$1$$$ до $$$2^h-1$$$ так, что вершина $$$1$$$ является корнем, а для любой нелистовой вершины $$$v$$$ её левым ребёнком является вершина $$$2v$$$, а правым ребёнком — вершина $$$2v+1$$$.
Изабель записывает бинарное значение (0 или 1) в каждую вершину дерева. Записав значение в каждую вершину, она отправляет получившееся дерево Таре.
Однако лорд Верити (их заклятый враг) попытается помешать их общению. После того как Изабель задаст значение каждой вершины, лорд Верити выполнит следующие действия в указанном порядке ровно один раз:
1. Он выберет некоторую вершину $$$u$$$.
2. Он инвертирует значение, записанное Изабель в вершине $$$u$$$. А именно, если Изабель записала 0 в вершине $$$u$$$, он заменит его на 1, и наоборот.
3. Если вершина $$$u$$$ является листом, больше он ничего не делает. Иначе он меняет местами указатели на детей вершины $$$u$$$. А именно, левый ребёнок $$$u$$$ одновременно становится правым, а правый ребёнок $$$u$$$ — левым. Затем все вершины перенумеровываются так, чтобы вершина $$$1$$$ была корнем, а для любой нелистовой вершины $$$v$$$ её левый ребёнок имел номер $$$2v$$$, а правый ребёнок — номер $$$2v+1$$$.
Обратите внимание, что действия лорда Верити могут быть адаптивными. Это означает, что выбираемая им для вмешательства вершина не фиксируется заранее и может зависеть от того, что Изабель запишет в дерево.
После вмешательства лорда Верити Тара получит структуру нового бинарного дерева и значение, записанное в каждой вершине. Она не знает, в какую вершину вмешался лорд Верити. Формально, она получает новую бинарную строку $$$l$$$, где $$$l_u$$$ — значение, записанное в вершине $$$u$$$ после перенумерации всех вершин.
Её задача — восстановить исходную строку $$$b$$$.
Возможны только две комбинации $$$n$$$ и $$$h$$$:
- $$$n = 1, h = 2$$$
- $$$n = 2030, h = 11$$$
Первая комбинация будет проверяться только в примерах, для которых приведена правильная стратегия.
Ваш код будет запущен ровно два раза на каждом тесте. При первом запуске вы будете Изабель, а при втором — Тарой.
Входные данные первого запуска
Первая строка входных данных содержит строку first. Она нужна, чтобы программа поняла, что это её первый запуск и она должна действовать как Изабель.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 1024$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$h$$$ ($$$n = 1$$$ и $$$h = 2$$$, либо $$$n = 2030$$$ и $$$h = 11$$$) — длину строки $$$b$$$ и высоту бинарного дерева соответственно. Обратите внимание, что комбинация $$$n = 1$$$ и $$$h = 2$$$ встречается только в примерах, но не в основных тестах.
Следующая строка содержит одну бинарную строку длины $$$n$$$, обозначающую $$$b$$$.
Входные данные второго запуска
Первая строка входных данных содержит строку second. Она нужна, чтобы программа поняла, что это её второй запуск и она должна действовать как Тара.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 1024$$$) — количество наборов входных данных. Далее следует описание наборов входных данных. Обратите внимание, что это число равно $$$t$$$ из входных данных первого запуска.
Первая строка каждого набора входных данных содержит ровно два целых числа $$$n$$$ и $$$h$$$ — длину бинарной строки $$$b$$$ и высоту соответствующего дерева. Порядок наборов входных данных может отличаться от порядка при первом запуске.
Вторая строка каждого набора входных данных содержит бинарную строку длины $$$2^h-1$$$, символами которой являются $$$l_1, l_2, \ldots, l_{2^h-1}$$$. Здесь $$$l_i$$$ обозначает значение вершины с номером $$$i$$$, определённое действиями Изабель и лорда Верити.
Обратите внимание, что после действий лорда Верити номера будут отличаться от номеров, которыми пользовалась Изабель.
Взломы
Для взломов используйте следующий формат.
Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 1024$$$) — число наборов входных данных.
Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$h$$$ и $$$p$$$ ($$$n = 2030$$$, $$$h = 11$$$, $$$1 \le p \le 2^h-1$$$) — длину строки $$$b$$$, высоту дерева и номер вершины, которую выбирает лорд Верити. Номер $$$p$$$ относится к нумерации дерева, использованной Изабель до действий лорда Верити.
Вторая строка каждого набора входных данных содержит бинарную строку $$$b$$$ длины $$$n$$$ — строку, которую должна передать Изабель.
Обратите внимание, что во взломах лорд Верити не действует адаптивно: он всегда выбирает вершину $$$p$$$ независимо от того, что запишет Изабель.
Выходные данные первого запуска
Для каждого набора входных данных выведите бинарную строку длины $$$2^h-1$$$, где $$$i$$$-й символ обозначает значение, которое Изабель записывает в вершину с номером $$$i$$$.
Выходные данные второго запуска
Для каждого набора входных данных выведите бинарную строку длины $$$n$$$ — предположение Тары о значении $$$b$$$.
first 2 1 2 0 1 2 1
000 101
second 2 1 2 010 1 2 001
1 0
При $$$n=1$$$ можно использовать следующую правильную стратегию.
Изабель хочет передать $$$1$$$ бит, но в её распоряжении есть $$$2^h-1=2^2-1=3$$$ вершины. Поскольку лорд Верити инвертирует значение только в одной вершине, правильная стратегия состоит в том, чтобы записать одно и то же значение $$$b_1$$$ во все вершины дерева. Затем Тара выводит значение, которое встречается в $$$l$$$ чаще всего.
Рассмотрим примеры. Обратите внимание, что порядок наборов входных данных при первом запуске не обязан совпадать с порядком при втором запуске. Здесь два набора входных данных поменяны местами.
Изабель и Тара используют описанную выше стратегию только для случая $$$b = 0$$$: Изабель записывает значение $$$0$$$ во все вершины дерева, поэтому она выводит $$$000$$$. Затем лорд Верити применяет свою операцию к вершине с номером $$$3$$$, и Тара получает $$$l = 001$$$. Поскольку $$$0$$$ встречается в $$$l$$$ чаще всего, она выводит $$$0$$$.
Другой случай, в котором $$$b = 1$$$, используется только для демонстрации влияния действия лорда Верити на дерево. А именно, Изабель решает записать значение $$$0$$$ в вершину $$$2$$$ и значение $$$1$$$ в вершины $$$1$$$ и $$$3$$$. Затем лорд Верити применяет свою операцию к вершине $$$1$$$. Сначала значение, записанное в вершине $$$1$$$, становится равным $$$0$$$. Затем два её ребёнка меняются местами и перенумеровываются: вершина $$$2$$$ получает номер $$$3$$$, а вершина $$$3$$$ получает номер $$$2$$$. Поэтому получается $$$l = 010$$$. Как по волшебству, Тара может правильно определить, что $$$b = 1$$$.
ВАЖНОЕ ПРИМЕЧАНИЕ: В этих примерах лорд Верити выбрал вершины $$$1$$$ и $$$3$$$. Однако при запуске вашего кода на примерах не гарантируется, что лорд Верити выберет те же вершины, поэтому не гарантируется, что вывод, совпадающий с выводом из примеров, будет правильным.
