Олимпиады

Кот Матроскин ждёт невероятно важное сообщение от своих родственников из Котинска. Но так как его родственники очень тревожные и боятся, что сообщение будет перехвачено, они его закодировали.

Кодирование, которое использовали коты, основано на том, что если какая-то подстрока уже встречалась ранее в строке, то на неё можно сослаться, указав, на сколько нужно сместиться относительно текущего элемента, чтобы попасть на первый символ нужной нам подстроки, и размер подстроки. Закодированное сообщение представляет из себя строку, в которой последовательно идут тройки элементов:

• первый элемент тройки — цифра, на которую нужно сместиться влево в раскодированной части исходной строки, чтобы получить первый символ повторяющейся ранее подстроки;
• второй элемент тройки — цифра, сколько символов нужно забрать (размер подстроки);
• третий элемент — буква, которая будет стоять за скопированной подстрокой.

Пример: закодированная строка 00a00b00c33d. Исходная строка будет строиться следующим образом:

• Изначально у нас пустая строка «».
• 00a: смещаемся на 0 символов влево и копируем подстроку длиной 0, после неё ставим символ a. Получилась строка «a».
• 00b: получилась строка «ab».
• 00c: получилась строка «abc».
• 33d: смещаемся на 3 символа влево и копируем подстроку длиной 3, после неё ставим символ d. Получилась строка «abcabcd».

«abcabcd» — раскодированная строка.

Матроскин получил одно и то же закодированное сообщение от двух родственников, но проблема в том, что оба родственника допустили по одной ошибке в своих кодах. Кот уже выяснил, что оба родственника ошиблись в записи третьего элемента одной из троек (каждый в своей тройке). Помогите Матроскину восстановить сообщение.

Полученные сообщения от родственников из Котинска:

• 00a00a00b00c31c11b73b00e00f00a
• 00a11b00c41c00c51c73e00f00a

Примечание: подстрокой называется непрерывная последовательность символов исходной строки. Например, «a», «bc» — будут подстроками для строки «abc».

Оля решила узнать у бабушки рецепт её фирменного печенья. Бабушка очень любит информатику, поэтому дала внучке список ингредиентов, записанный с помощью 7 логических высказываний, и сказала, что одно из них ложно, а остальные истинны. Логические высказывания:

• Если 33 в троичной системе записывается как 1010, то муки нужно использовать на 3 стакана больше, чем сахара.
• Если мука и сахар используются в равных пропорциях, то растопленного сливочного масла нужно использовать в 4 раза меньше, чем использовалось муки.
• Сахара нужно взять на 2 стакана меньше, чем муки.
• Растопленного сливочного масла используется в 2 раза меньше, чем муки.
• Муки используется в 2 раза больше, чем сахара.
• Число стаканов сахара является минимальным числом в двоичной системе счисления, содержащим хотя бы одну единицу и хотя бы один ноль в значащих разрядах.
• Если используется 2 стакана сахара, то существует ровно 1 система счисления, запись в которой количества стаканов муки будет начинаться с цифры 1.

Примечание: все ингредиенты отмеряются с помощью стакана, каждого ингредиента используется целое положительное количество стаканов.

Сколько стаканов муки нужно использовать, чтобы приготовить бабушкино фирменное печенье? В ответ запишите одно число — количество стаканов муки.

У Кота Матроскина проблема. У него есть следующее логическое выражение, зависящее от трёх переменных:

X₀(А, В, С) = (А И НЕ(В)) ИЛИ (А И НЕ(А) И НЕ(С)) ИЛИ (С И В И НЕ(А) И НЕ(С)) ИЛИ С

Над этим выражением ему нужно проделать следующий алгоритм. Первоначальное значение i = 1, и после каждого вычисления выражения значение i увеличивается на 1.

1. Вычислить выражение Xᵢ, подставив Xᵢ₋₁ в данное выражение:
   Xᵢ(А, В, С) = (С И Xᵢ₋₁(А, В, 1)) ИЛИ (НЕ(С) И Xᵢ₋₁(А, В, 0))
2. Повторить первый пункт 10 раз.
3. Вычислить выражение Xᵢ, подставив Xᵢ₋₁ в данное выражение:
   Xᵢ(А, В, С) = (А И Xᵢ₋₁(1, В, С)) ИЛИ (НЕ(А) И Xᵢ₋₁(0, В, С))
4. Повторить третий пункт 10 раз.
5. Вычислить выражение Xᵢ, подставив Xᵢ₋₁ в данное выражение:
   Xᵢ(А, В, С) = (В И Xᵢ₋₁(А, 1, С)) ИЛИ (НЕ(В) И Xᵢ₋₁(А, 0, С))
6. Повторить пятый пункт 10 раз.

Под слагаемым подразумевается переменная / переменная с отрицанием / константа или последовательность из переменных / переменных с отрицаниями / констант, соединённых операцией И. Примерами слагаемых являются: А И В И С — 1 слагаемое, А И НЕ(В) — 1 слагаемое. Пример: в выражении А ИЛИ В ИЛИ С — 3 слагаемых, (А И НЕ(В) И 1) ИЛИ (0 И А) — 2 слагаемых.

Важное примечание! Изначальную формулу X₀ изменять нельзя. Для каждого из пунктов вычисление происходит по следующим правилам (X, Y, Z — любые переменные или функции):

• Раскрываем скобки по правилу: X И (Y ИЛИ Z) = (X И Y) ИЛИ (X И Z).
• Исключаем слагаемые, следуя правилам, описанным ниже:
  • если внутри одного слагаемого есть 0, то это слагаемое исключаем;
  • если есть повторяющиеся слагаемые — оставляем только одно, остальные исключаем;
  • если в слагаемом одновременно встречаются X и НЕ(X) — слагаемое исключаем;
  • НЕ(1) = 0, НЕ(0) = 1;
  • 1 И X = X;
  • слагаемые можно менять местами, так же, как и порядок переменных в слагаемом;
  • делаем так, пока можно что-то исключить;
  • правила, не описанные в этом списке, применять строго запрещено!

Сколько слагаемых получится в итоговом выражении?

Даны два числа: \(A = (120x)_4\) и \(B = (130y)_5\), где x и y — неизвестные цифры в системах счисления с основаниями 4 и 5 соответственно. Известно, что для чисел A и B выполняются два условия:

• \(A + B\) кратно \(7_{10}\);
• \(|A - B|\) минимально при выполнении всех остальных условий задачи.

Найдите пару чисел A и B, удовлетворяющую условиям. В ответе укажите A и B, записанные в десятичной системе счисления через пробел (сперва A, потом B). Пример ответа: «33 149».

Наташа забыла свой пароль, состоящий из двух цифр. Она помнит, что:

• Пароль состоит из двух десятичных цифр.
• В восьмеричной системе пароль записывается ровно тремя символами (без ведущих нулей).
• В шестнадцатеричной системе пароль записывается ровно двумя символами (без ведущих нулей).
• Сумма десятичных цифр пароля равна 7.
• Требуется наименьшее десятичное число, удовлетворяющее условиям.

Найдите значение пароля, ответ запишите в десятичной системе счисления.

В стопке лежат билеты для экзамена по дискретной математике в ИТМО. В стопке 7 билетов: три на «A», два на «B», два на «C». Буквы обозначают тип (тему) билета. Билеты одного типа между собой неразличимы. Студенты подходят по очереди, ассистент каждый раз выдаёт верхний билет из стопки.

Правило: если сейчас должны выдать билет, и у двух предыдущих студентов уже были выданы «A» и «A» (то есть подряд уже было две «A»), и сейчас сверху тоже лежит «A», то перед выдачей ассистент перемешивает верхние три билета в произвольном порядке и затем тут же выдаёт верхний из этих трёх, даже если это снова оказался «A» — повторной проверки и дополнительного перемешивания в тот же момент не происходит. Если условие не выполняется, ассистент просто выдаёт верхний билет.

Сколько различных последовательностей выдачи этих 7 билетов можно получить при таком правиле, если исходный порядок стопки любой, а при перемешивании ассистент может выбрать любой порядок верхних трёх?

В ответе укажите целое число.

Какие симметричные алгоритмы шифрования считаются безопасными для использования в современном мире? В ответе запишите все возможные варианты через пробел. Пример ответа: «1 2 3».

1. AES
2. RSA
3. MD5
4. SHA-256
5. Serpent

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

Данные о клиенте. Максимальный бюджет — 10 500 рублей. Предпочтения клиента — для выбора маршрута важны три ключевых критерия, из которых хотя бы два должны быть выполнены: красивые виды, хороший отель, экскурсии и развлечения. Дата, до которой клиент хочет улететь — 01.07.2026 (это крайний срок, до которого клиент готов ждать рейс, рейсы позже он не будет рассматривать ни при каких обстоятельствах). Желаемой даты нет: учитывается «сегодняшняя дата» и крайний срок.

Дополнительные затраты. Если клиент решит подождать более поздний рейс (но до 01.07.2026), ему нужно будет заплатить дополнительную сумму за каждый день использования нашего агентства (800 рублей за день).

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

Ваш босс поставил задачу получить максимальную выручку для агентства. Иногда может быть выгодно заставить клиента подождать рейс, чтобы выбрать более прибыльный маршрут. Выручкой считать все деньги, которые клиент выплатит агентству: стоимость маршрута + при необходимости плата за дни использования агентства во время ожидания рейса. Количество дней использования агентства = max(0; Дата начала рейса − Сегодняшняя дата).

За «сегодняшнюю дату» при расчётах брать 18.06.2026. В ответе укажите два числа через пробел: номер выбранного маршрута и общую выручку, которую агентство получит от этого маршрута.

В столовой ИТМО стоит 2 PlayStation. Начинается борьба за PlayStation, но студенты ИТМО — приличные люди, поэтому они соблюдают правила очереди. Каждый раз, когда студент или пара друзей решают поиграть на одной из консолей, они создают заявку в ИСУ (электронная система университета), становясь частью очереди на использование PlayStation. Заявка содержит следующую информацию:

1. имя студента (или пары студентов);
2. время прихода (целое, номер минуты);
3. длительность игры первого игрока (минуты);
4. длительность игры второго игрока (минуты).

(Если один закончил раньше, второй продолжает играть один; консоль освобождается, когда закончит последний.)

Правила очереди:

• Когда PlayStation освобождается, система ИСУ автоматически выбирает следующую заявку из очереди ожидания, и доступ к PlayStation получают создатели этой заявки.
• Выбирается заявка с минимальным временем прихода (пришла раньше).
• Если время прихода одинаково, выбирается та, что раньше во входных данных.
• Если в момент освобождения никто не ждёт, консоль простаивает до следующего прихода.
• Если одновременно свободны несколько PlayStation, заявки распределяются по консолям в порядке их номеров (1, 2, …).

В один день в столовой ИТМО было подано 8 заявок на использование PlayStation. Отсчёт времени начинается с 0 в момент запуска электронной системы для создания заявок и идёт в минутах; первая заявка пришла спустя 1 минуту после запуска. Время ожидания заявки — это период, прошедший с момента подачи заявки, но до того, как её инициаторы начали играть на PlayStation. Общее время ожидания — это сумма времени ожидания всех заявок.

Вам дана таблица заявок студентов:

Вам нужно вывести два числа через пробел:

1. Общее время ожидания всех заявок.
2. Номер минуты, когда освободилась последняя PlayStation, после завершения последней заявки.

Пример записи ответа: «12 34».

Дана блок-схема алгоритма:

(тут должно быть изображение)

Известно, что на вход алгоритма подаются целые положительные x, но не гарантировано, что алгоритм завершит свою работу для любых x. Какое наименьшее x нужно подать на вход, чтобы алгоритм завершил свою работу и на выходе было получено число 2026?

Примечание: a mod b — остаток от деления a на b; a div b — целочисленное деление a на b.

Граф — это множество вершин (обозначаются на схемах точками или кругами), некоторые из которых соединены между собой рёбрами (обозначаются на схемах линиями). Бинарным деревом называют такой граф, на который наложен ряд ограничений:

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

Примеры бинарных деревьев (корень показан как вершина с номером 1):

(тут должно быть изображение)

Будем называть высотой бинарного дерева максимальное возможное в этом дереве количество рёбер, которое может потребоваться пройти от корня дерева, чтобы добраться до какой-либо вершины графа (при этом нельзя дважды проходить через одно и то же ребро или одну и ту же вершину). На картинках выше изображены бинарные деревья высотой 2.

Петя и Витя решили сыграть в игру по строительству бинарного дерева. Перед началом игры в их бинарном дереве содержится ровно 1 вершина, являющаяся корнем этого дерева. В свой ход игрок на свой выбор добавляет в бинарное дерево либо одну вершину, связывая её ребром с одной из уже существующих в дереве вершин, либо две вершины, связывая их рёбрами также с одной из уже существующих в дереве вершин. При добавлении вершин и рёбер игроки не могут нарушать ограничений построения графа-бинарного дерева.

Примеры допустимых ходов (чёрным показан граф на момент начала хода игрока, зелёным выделены рёбра и вершины, которые он добавил в свой ход):

(тут должно быть изображение)

Назовём полным бинарным деревом высоты h такое бинарное дерево, в которое не может быть добавлена ни одна вершина с ребром так, чтобы высота дерева не увеличилась.

Победителем в игре будет считаться игрок, в чей ход бинарное дерево превратится в полное бинарное дерево высоты 12. Игроки также договорились, что ни в какой момент игры высота дерева не должна стать больше 12. Первым ходит Петя. Кто может победить в такой игре независимо от ходов противника?

В ответ запишите два числа через пробел без кавычек: номер игрока, который может победить независимо от ходов противника (1 — Петя, 2 — Витя) и максимальное количество ходов, которые может потребоваться выполнить этому игроку для победы. Пример записи ответа, если выиграть может Петя своим вторым ходом независимо от ходов противника: «1 2».

Недавно в ИТМО произошли изменения номеров аудиторий, но вот незадача — в вашем расписании остались старые номера. Чтобы получить новые номера аудиторий и попасть на все занятия, вы можете воспользоваться следующей логикой:

Если номер не заканчивается на 0, из него вычитается 50. Затем, независимо от этого, мы всегда уменьшаем номер на 100.

Далее, в зависимости от суммы цифр номера аудитории, полученного на предыдущем шаге, применяются разные действия. Если сумма цифр чётная, номер становится равным квадратному корню из самого себя (округлённому до целого по правилам арифметического округления). Если сумма цифр нечётная, к номеру прибавляется остаток от деления на 7.

Далее, если в номере присутствует цифра 7, это требует особого внимания: в таком случае номер умножается на остаток от деления этого номера на 5, увеличенный на 1. Если цифры 7 нет, номер делится на 3 (целочисленно).

Для каждого номера нужно выполнить 3 итерации этого алгоритма, чтобы получить новый номер аудитории.

Список номеров аудиторий из вашего расписания: 483, 3198, 9801, 1944.

Ваша задача — вычислить новые номера аудиторий и вывести их в порядке возрастания через пробел.

Пример ответа: 4 100 200 300

Сколько существует последовательностей из 8 битов, для которых выполняется следующее равенство:

A(X) ИЛИ B(X) = ИСТИНА

Где X — последовательность из 8 битов, т.е. \(X = (x_0, x_1, x_2, x_3, x_4, x_5, x_6, x_7)\). A(X), B(X) — логические выражения, заданные следующим образом:

\(A(X) = (x_0 \oplus x_4) \wedge (x_1 \oplus x_5) \wedge (x_2 \oplus x_6) \wedge (x_3 \oplus x_7)\)

\(B(X) = (x_0 \wedge x_1) \vee (x_1 \wedge x_2) \vee (x_2 \wedge x_3) \vee (x_3 \wedge x_4) \vee (x_4 \wedge x_5) \vee (x_5 \wedge x_6) \vee (x_6 \wedge x_7)\)

Здесь \(\oplus\) обозначает XOR (Исключающее ИЛИ), \(\wedge\) — И (конъюнкцию), \(\vee\) — ИЛИ (дизъюнкцию).

Примечание. Таблица истинности для XOR:

В ответе укажите целое число.

Компьютерщик Артур собирает серверный стенд для запуска вычислительного кластера. Стенд имеет размер 2×2×5:

(тут должно быть изображение)

• 2 уровня (верхний и нижний),
• на каждом уровне — 2 ряда по 5 слотов.

Всего в стенде 20 слотов. Артуру нужно установить 3 одинаковых мощных GPU-узла. Артур знает, что, если два мощных GPU окажутся слишком близко, система перегреется. Поэтому два GPU-узла не могут находиться в соседних по грани слотах.

Соседними считаются слоты:

• слева или справа в одном ряду,
• спереди или сзади в пределах одного уровня,
• строго над или под друг другом между уровнями.

Расположение по диагонали допустимо. Пример допустимого расположения узлов:

(тут должно быть изображение)

Сколькими способами Артур может установить 3 GPU-узла так, чтобы не нарушить правило охлаждения? В ответ укажите единственное число.

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

Для кодирования числа n подбирается такая сумма степеней двойки, чтобы в сумме получилось число n. При этом каждую из степеней двойки можно домножить на любую цифру от 0 (включительно) до 9 (включительно). Таким образом, многие числа можно представить как сумму степеней, домноженных на разные цифры, разными способами, например:

\(39 = 2^5 \cdot 1 + 2^0 \cdot 7 = 2^4 \cdot 2 + 2^0 \cdot 7 = 2^4 \cdot 2 + 2^2 \cdot 1 + 2^0 \cdot 3 = \ldots\)

После того как для числа n подобраны степени двойки и цифры, на которые эти степени домножаются, определяется максимальная степень двойки, которая участвует в сумме, и к этому числу прибавляется «1» — столько разрядов будет в финальном числе, обозначим это количество разрядов как r. Далее разряды закодированного числа нумеруются с 0 и до r−1. На каждую позицию записывается цифра, на которую домножалась соответствующая степень двойки.

Например, если сумма 39 была подобрана как \(2^5 \cdot 1 + 2^0 \cdot 7\), то количество разрядов r = 5+1 = 6, и число записывается в виде 700001. А если сумма 39 была подобрана как \(2^4 \cdot 2 + 2^2 \cdot 1 + 2^0 \cdot 3\), то число будет записано уже в виде 30102.

Теперь Вася задался вопросом, как закодировать своим способом число 71 так, чтобы сумма цифр результата кодирования при интерпретировании его как десятичного числа была минимальным возможным числом. В ответ запишите одно число — результат кодирования.

Пример: для числа 2 возможно две записи: \(2 = 2^1 \cdot 1\) (запись 01) и \(2 = 2^0 \cdot 2\) (запись 2). При интерпретации чисел 01 и 2 в десятичной системе получаем суммы цифр 0+1 = 1 и 2, из них минимальна 1, значит в ответ было бы нужно записать «01».

Света и Костя обсуждают новую образовательную программу в переписке. Формулировки важны, а интернет иногда «шалит»: при передаче сообщения один бит может исказиться. Чтобы восстанавливать смысл, они решили кодировать каждый фрагмент сообщения кодом Хэмминга (7,4), который умеет исправлять ровно одну ошибку.

Каждый фрагмент состоит из 4 информационных битов d1 d2 d3 d4. Они кодируются в 7-битное слово, где позиции нумеруются слева направо от 1 до 7:

• позиции 1, 2, 4 — проверочные биты p1, p2, p4;
• позиции 3, 5, 6, 7 — данные d1, d2, d3, d4.

То есть буква имеет вид (индексация с 1):

Проверка. Для проверки сначала вычисляются s1, s2, s4 с помощью XOR (Исключающее ИЛИ, обозначается как ⊕):

• s1 = p1 ⊕ d1 ⊕ d2 ⊕ d4 (позиции 1, 3, 5, 7)
• s2 = p2 ⊕ d1 ⊕ d3 ⊕ d4 (позиции 2, 3, 6, 7)
• s4 = p4 ⊕ d2 ⊕ d3 ⊕ d4 (позиции 4, 5, 6, 7)

Далее рассчитывается синдром ошибки S: S = s1·1 + s2·2 + s4·4.

• если S = 0, ошибки нет;
• иначе ошибочен бит в позиции S (его нужно инвертировать: 0→1 или 1→0).

Гарантируется, что в каждом принятом фрагменте либо нет ошибок, либо ровно одна ошибка на фрагмент.

Вам дано закодированное слово (состоит из нескольких фрагментов):

1010101 0111110 1100000 0011001 0110101

В ответ запишите пару чисел «номер фрагмента с ошибкой» и «номер бита с ошибкой в этом фрагменте» (без пробела между этими двумя числами); если таких пар несколько, то запишите эти пары через пробел в том же порядке, в котором фрагменты даны в условии (индексация с 1 как для бита, так и для номера фрагмента).

Пример записи ответа: 11 27

Примечание. Таблица истинности для XOR (Исключающего ИЛИ):

Процессор читает инструкции переменной длины и работает в две стадии:

1) Выборка. За 1 такт процессор может считать из памяти ровно 8 байт (даже если какая-то инструкция при этом считается не полностью) и положить их в буфер выборки. Размер буфера выборки — 16 байт.

Буфер выборки работает как циклическая очередь. Если в буфере нет места для новых данных, они записываются поверх старых, уже декодированных данных, начиная с начала буфера, что позволяет не терять последние считанные байты. Точно так же — циклически — происходит последующее чтение данных из буфера. Если в буфере нет места для ещё 8 байт (в буфере уже находится более 8 ещё не декодированных байт), выборка в этот такт не выполняется. Байты поступают в конец буфера и читаются с начала, как в очереди.

2) Декодирование. Инструкции декодируются строго по порядку. Время декодирования зависит от длины инструкции:

• 2 байта = 1 такт
• 4 байта = 2 такта
• 8 байтов = 3 такта

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

Программа состоит из 1000 инструкций: 40% — длиной 2 байта, 30% — длиной 4 байта, 30% — длиной 8 байт.

Задание: найдите общее количество тактов до момента, когда последняя инструкция будет полностью декодирована.

Андрей — студент ИТМО. Он очень любит гулять по Санкт-Петербургу. Город представляет собой граф из \(n\) перекрёстков и \(m\) улиц, по улицам можно ходить в обе стороны.

После каждой прогулки Андрей оценивает, насколько ритмичной она получилась. Он считает, что у прогулки есть ритм \(k\), если число улиц, которые он прошёл, кратно \(k\). Андрей может проходить по одной и той же улице несколько раз (даже подряд).

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

Маршрут — такая последовательность вершин \(a_1, \dots, a_t\), \(t>1\), что соседние вершины соединены ребром (рёбра и вершины могут повторяться). Длина такого маршрута считается равной \(t-1\).

Вы должны помочь ему и ответить на \(q\) запросов.

Формат входных данных

В первой строке даны числа \(n\) и \(m\) — количество перекрёстков и улиц (\(1 \le n \le 10^5,\ 0 \le m \le 10^5\)). В последующих \(m\) строках дано описание графа, по два числа в строке \(v\) и \(u\) — улица, соединяющая вершины \(v\) и \(u\) (\(1 \le v, u \le n\)). В графе могут присутствовать петли и кратные рёбра. В следующей строке дано число \(q\) — количество вопросов (\(1 \le q \le 10^5\)). В последующих \(q\) строках дано по три числа \(v, u, k\) — стартовый и конечный перекрёсток и требуемая ритмичность прогулки (\(1 \le v, u \le n,\ 1 \le k \le 10^6\)).

Формат выходных данных

Выведите \(q\) строк. В \(i\)-й строке — ответ на \(i\)-й запрос: Yes, если существует маршрут с ритмичностью \(k\), и No иначе.

Васе очень нравится игра «2048», но ему не хватает в ней гибкости. Он решил создать свою версию, где размер доски, возможные номиналы плиток и цель игры могут меняться. Ваша задача — написать движок-валидатор для этого турнира.

Игра происходит на квадратном поле размера \( X \times X \) (в данной задаче \( X = 5 \)).

• Слияние. При сдвиге в одном из четырёх направлений плитки с одинаковым номиналом объединяются, если они «налетают» друг на друга. Номинал новой плитки равен сумме двух предыдущих. Одна плитка не может участвовать в слиянии дважды за один ход. Порядок слияния соответствует классической игре 2048. К примеру, строка 22200 при сдвиге вправо превратится в 00024. Под нулём подразумеваются пустые клетки.
• Ход. Считается совершённым, если хотя бы одна плитка изменила своё положение или произошло слияние.
• Очерёдность. После каждого успешного хода на поле должна появиться новая плитка.

Формат входных данных

В первой строке содержится целое число \( n \) (\( 1 \le n \le 10 \)) — количество возможных номиналов новых плиток.

Во второй строке содержатся \( n \) целых различных чисел \( a_1, a_2, \ldots, a_n \) (\( 2 \le a_i \le 2^{10} \)) — доступные номиналы для новых плиток. Гарантируется, что \( a_i \) — степень двойки.

В третьей строке содержится целое число \( m \) (\( 2^{11} \le m \le 2^{20} \)) — минимальная стоимость плитки для победы.

В четвёртой строке содержится целое число \( q \) (\( 2 \le q \le 10^4 \)) — количество запросов.

Далее следуют \( q \) запросов. Каждый запрос начинается с типа операции \( T \). Номер запроса \( x \) считается с нуля.

Типы запросов:

• Тип 1. Вывести текущее состояние доски в виде матрицы \( X \times X \). Пустые клетки выводятся как 0.
• Тип 2 (Появление). На следующей строке даны \( x, y, b \): \( x, y \) — координаты (\( 0 \le x, y < X \)); \( b \) — номинал (\( 2 \le b \le 2^{10} \)).
• Тип 3 (Ход). На следующей строке дано число \( d \) — направление: 0 — вверх, 1 — вправо, 2 — вниз, 3 — влево.

Примечание. Гарантируется, что самым первым игровым запросом будет запрос типа 2. Проверка на поражение производится сразу после появления новой плитки.

Формат выходных данных

На каждый запрос первого типа нужно вывести 5 строк по 5 чисел через пробел — доску с плитками. Если плитка пустая, следует вывести 0.

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

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

Дана операционная система семейства GNU/Linux. Известны результаты последовательного выполнения нескольких команд в некотором текущем каталоге.

В результате выполнения команды ls -Rl был получен следующий вывод:

В результате выполнения команды cat $(find -type f) 2>/dev/null были последовательно, каждая в своей строке, выведены буквы английского алфавита от a до r.

Известно, что файл с именем file211 содержит символ a, файл с именем file21 содержит символ g, а файл с именем file3 содержит символ r.

Затем были последовательно выполнены ещё три команды:

chmod 222 $(find -type f -regex ".+file.*[13]+")
chmod 664 $(find -type f -regex ".+file.*[23]+1")
cat $(find -type f) 2>/dev/null

Какие символы будут выведены в результате выполнения последней команды? В ответе укажите их подряд без пробелов в алфавитном порядке.

Примечания:

• ls -Rl — команда, рекурсивно выводящая содержимое текущего и всех вложенных каталогов, включая информацию о типе (каталог или регулярный файл) и правах доступа.
• cat $(find -type f) 2>/dev/null — команда, рекурсивно обходящая все подкаталоги и выводящая содержимое всех найденных файлов с игнорированием сообщений об ошибках доступа.
• chmod ### $(find #####) — команда, применяющая маску прав доступа (три восьмеричных числа, соответствующих битам прав на чтение, запись и исполнение для владельца, группы и всех пользователей) для файлов, которые найдёт команда find.
• Ключ -type f у команды find выводит только полные имена регулярных файлов.
• Ключ -regex позволяет выводить только полные имена файлов, соответствующих регулярному выражению.

Специальные символы регулярных выражений: . — любой символ; [] — диапазон допустимых символов (например, [abc]); + — предыдущий символ повторяется 1 или более раз; * — предыдущий символ повторяется 0 или более раз.

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