2026-2027 Всероссийская командная олимпиада школьников по программированию, СПбКОШП + интернет-тур + отборы регионов (ВКОШП 26, СПбКОШП + интернет-тур)
A. Ножки для олимпиады
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Костя готовит площадку для командной олимпиады. Каждой команде нужен стол и три табуретки.

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

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

  1. Собирает три табуретки, если на них хватает ножек.
  2. Если получилось собрать три табуретки, он собирает один стол, если на него хватает ножек.
  3. Повторяет действия 1 и 2, пока хватает ножек.
  4. Если на действия 1 или 2 не хватает ножек, он собирает из всех оставшихся ножек максимально возможное количество табуреток и останавливается. Эти табуретки будут запасными на случай поломки во время олимпиады.

Костя очень занят сборкой мебели, помогите ему ответить на вопрос, сколько столов и табуреток у него получится собрать.

Входные данные

На первой строке ввода дано число $$$n$$$ ($$$1 \le n \le 10^{18}$$$).

Выходные данные

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

Примеры
Входные данные
3
Выходные данные
0 1
Входные данные
18
Выходные данные
1 4
B. Ключ от сейфа
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В Центральном банке Берляндии клиенты хранят свои деньги и ценности в ячейках в большом сейфе. Чтобы войти в сейф, клиент набирает личный секретный код, который представляет собой $$$n$$$ последовательных неотрицательных целых чисел.

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

У Родиона, постоянного клиента банка, истекает действие его секретного кода $$$A=[a_1, a_2, \ldots, a_n]$$$. Он придумал новый секретный код $$$B=[b_1, b_2, \ldots, b_n]$$$. Услуга изменения секретного кода в банке выглядит так: чтобы Родиону преобразовать старый код $$$A$$$ в новый $$$B$$$, он произвольное число раз может выполнить следующую операцию.

Выбрать целое число $$$k$$$ ($$$0 \le k \lt 40$$$). Для каждого элемента текущего кода $$$A$$$ выбирается одно из двух действий:

  • бесплатно заменить $$$a_i$$$ на $$$a_i \bmod 2^k$$$;
  • оставить $$$a_i$$$ без изменений и заплатить $$$2^k$$$ монет.

Стоимость операции равна сумме монет, заплаченных за все элементы, оставленные без изменений в этой операции.

Конечно, Родиону хочется заплатить за изменение кода поменьше. Помогите ему найти минимальную суммарную стоимость операций, после которых старый код $$$A$$$ станет равен новому коду $$$B$$$.

Если преобразовать код $$$A$$$ в код $$$B$$$ невозможно, выведите $$$-1$$$.

Входные данные

Тест содержит один или несколько наборов входных данных. В первой строке дано целое число $$$t$$$ — количество наборов входных данных ($$$1 \le t \le 1000$$$). Далее следуют описания наборов входных данных.

В первой строке каждого набора дано целое число $$$n$$$ — длина кода ($$$1 \le n \le 2 \cdot 10^5$$$).

Во второй строке даны $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$, а в третьей строке — $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \le a_i, b_i \lt 2^{40}$$$).

Сумма значений $$$n$$$ по всем наборам входных данных в одном тесте не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных требуется вывести одно целое число — минимальную суммарную стоимость преобразования кода $$$A$$$ в код $$$B$$$. Если преобразование невозможно, требуется вывести $$$-1$$$.

Пример
Входные данные
4
2
1 7
0 1
3
3 1 4
1 5 9
4
13 10 4 4
1 2 4 4
2
1099511627775 549755813888
7 549755813888
Выходные данные
1
-1
6
8
Примечание

В первом примере можно выполнить следующие операции:

  1. Выбрать $$$k = 2$$$: заменить $$$a_1 = 1$$$ на $$$a_1 \bmod 2^2 = 1$$$ и $$$a_2 = 7$$$ на $$$a_2 \bmod 2^2 = 1$$$, после чего код принимает вид $$$A = [1, 1]$$$. Эта операция бесплатна.
  2. Выбрать $$$k = 0$$$: заменить $$$a_1 = 1$$$ на $$$a_1 \bmod 2^0 = 0$$$, а $$$a_2 = 1$$$ оставить без изменений и заплатить $$$2^0 = 1$$$ монету. Стоимость этой операции равна $$$1$$$. После этой операции код $$$A = [0, 1]$$$.

Итоговая суммарная стоимость равна $$$1$$$. Не существует последовательности операций меньшей стоимости, после которой код $$$A$$$ станет равен коду $$$B$$$.

Во втором примере выполнить требуемое преобразование невозможно.

C. Бассейн
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Александр решил построить себе бассейн около дома и попросил дизайнеров подготовить его проект.

Дизайнеры предложили бассейн в форме выпуклого многоугольника с вершинами в точках $$$P_1, P_2, \ldots, P_n$$$. Вершина $$$P_i$$$ имеет координаты $$$(x_i, y_i)$$$. Вершины перечислены в порядке обхода против часовой стрелки; никакие три вершины не лежат на одной прямой. Известно, что $$$x_1 \lt x_2 \lt \ldots \lt x_n$$$, все $$$y_i \le 0$$$ и $$$y_1 = y_n = 0$$$.

Оценив стоимость работ, Александр решил упростить проект: новый бассейн должен иметь форму выпуклого многоугольника ровно с $$$k$$$ вершинами. Однако рабочие уже перенесли разметку на участок и даже начали копать, поэтому расположение бассейна нельзя выбрать произвольно. Бассейн должен иметь форму выпуклого многоугольника и целиком содержать многоугольник, в котором бассейн планировалось разместить исходно. Каждая сторона бассейна должна лежать на одной из прямых, содержащих стороны исходного многоугольника. Для разных сторон нового бассейна необходимо использовать разные прямые. Кроме того, строительство стенки вдоль стороны $$$P_1P_2$$$ уже началось, поэтому одна из сторон нового бассейна обязательно должна лежать на прямой, проходящей через вершины $$$P_1$$$ и $$$P_2$$$.

При этом участок Александра не слишком большой, поэтому он хочет построить бассейн минимальной площади, удовлетворяющий этим условиям.

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

Помогите ему найти минимально возможную площадь нового бассейна, удовлетворяющего всем требованиям.

Входные данные

В первой строке даны два целых числа $$$n$$$ и $$$k$$$ — количество вершин исходного многоугольника и необходимое количество вершин нового бассейна ($$$3 \le k \le n \le 10^5$$$).

В каждой из следующих $$$n$$$ строк даны два целых числа $$$x_i$$$ и $$$y_i$$$ — координаты вершины $$$P_i$$$ ($$$-10^9 \le x_i \le 10^9$$$, $$$-10^9 \le y_i \le 0$$$).

Гарантируется, что точки являются вершинами выпуклого многоугольника и перечислены в порядке обхода против часовой стрелки. Никакие три вершины многоугольника не лежат на одной прямой. Также гарантируется, что $$$x_1 \lt x_2 \lt \ldots \lt x_n$$$ и $$$y_1 = y_n = 0$$$.

Выходные данные

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

Ответ считается правильным, если его абсолютная или относительная погрешность не превышает $$$10^{-6}$$$.

Примеры
Входные данные
4 3
0 0
1 -1
2 -1
3 0
Выходные данные
2.25
Входные данные
4 4
0 0
1 -1
2 -1
3 0
Выходные данные
2
Примечание

В первом примере новый бассейн должен иметь ровно три стороны. Оптимальным решением является треугольник $$$AED$$$. Его стороны лежат на прямых, содержащих стороны $$$AB$$$, $$$CD$$$ и $$$AD$$$ исходного многоугольника. Площадь этого треугольника равна $$$2.25$$$. Полученный бассейн изображён на рисунке слева.

Во втором примере новый бассейн должен иметь ровно четыре стороны, поэтому можно оставить исходный многоугольник без изменений. Его площадь равна $$$2$$$. Полученный бассейн изображён на рисунке справа.

D. A+B
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В своей старой тетради Ксюша нашла три числа $$$A$$$, $$$B$$$, $$$C$$$ и равенство $$$A + B = C$$$, которое ей показалось довольно подозрительным.

Ксюша поняла, что числа, вероятно, записаны в какой-то альтернативной системе счисления и решила найти все возможные целые основания систем счисления $$$b \ge 2$$$, при которых все три записи чисел корректны и равенство верно. Так как таких систем счисления может быть много, она решила вычислить сумму их оснований.

Помогите Ксюше вычислить искомую сумму. Если таких оснований бесконечно много, сообщите об этом.

Напомним, что запись числа в системе счисления с основанием $$$b$$$ задаётся массивом цифр $$$d_1, d_2, \ldots, d_n$$$, от старшего разряда к младшему. Она корректна, если $$$0 \le d_i \lt b$$$ для всех $$$1 \le i \le n$$$. Значение числа, заданного цифрами $$$d_1, d_2, \ldots, d_n$$$ в системе счисления с основанием $$$b$$$ равно $$$$$$\sum_{i=1}^{n} d_i b^{n-i}.$$$$$$ Традиционно для систем счисления с основанием больше $$$10$$$ для записи цифр используются буквы и другие значки, но в этой задаче мы просто зададим значения каждой цифры в записи чисел, не вводя специальных обозначений.

Входные данные

Первая строка содержит целое число $$$n_A$$$ — длину записи числа $$$A$$$ ($$$1 \le n_A \le 10^5$$$). Вторая строка содержит $$$n_A$$$ целых чисел $$$a_1, a_2, \ldots, a_{n_A}$$$ — значения её цифр ($$$0 \le a_i \le 10^9$$$).

Третья строка содержит целое число $$$n_B$$$ — длину записи числа $$$B$$$ ($$$1 \le n_B \le 10^5$$$). Четвёртая строка содержит $$$n_B$$$ целых чисел $$$b_1, b_2, \ldots, b_{n_B}$$$ — значения её цифр ($$$0 \le b_i \le 10^9$$$).

Пятая строка содержит целое число $$$n_C$$$ — длину записи числа $$$C$$$ ($$$1 \le n_C \le 10^5$$$). Шестая строка содержит $$$n_C$$$ целых чисел $$$c_1, c_2, \ldots, c_{n_C}$$$ — значения её цифр ($$$0 \le c_i \le 10^9$$$).

Цифры каждой записи перечислены от старшего разряда к младшему.

Гарантируется, что записи чисел не содержат ведущих нулей.

Выходные данные

В единственной строке выведите сумму всех целых оснований $$$b \ge 2$$$, при которых записи чисел $$$A$$$, $$$B$$$ и $$$C$$$ корректны и выполняется равенство $$$A + B = C$$$.

Если таких оснований нет, выведите $$$0$$$. Если их бесконечно много, выведите строку «inf».

Примеры
Входные данные
2
1 2
1
3
2
2 0
Выходные данные
5
Входные данные
2
1 2
2
3 4
2
4 6
Выходные данные
inf
Входные данные
2
1 2
1
0
2
2 0
Выходные данные
0
E. Пишущая машинка из будущего
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Даню назначили главным редактором школьной стенгазеты в ретро-стиле. Для аутентичности Даня решил набирать ее на пишущей машинке. Старую пишущую машинку Дане найти не удалось, поэтому он заказал в онлайн-магазине современную программируемую пишущую машинку.

Клавиатура машинки представляет собой $$$m$$$ клавиш, расположенных в один ряд и пронумерованных от $$$1$$$ до $$$m$$$. Дане для очередного выпуска стенгазеты нужно набрать текст $$$s = s_1 s_2 \ldots s_n$$$, состоящий из первых $$$m$$$ строчных букв английского алфавита. Машинку можно программировать под свой текст. Для этого каждую из $$$m$$$ букв нужно назначить ровно одной клавише, причём разные буквы должны находиться на разных клавишах. Если две последовательные буквы текста расположены на клавишах с номерами $$$x$$$ и $$$y$$$, то время перехода между ними равно $$$|x - y|$$$. Время набора первой буквы не учитывается. Таким образом, если символ $$$c$$$ расположен на позиции $$$p_c$$$, то полное время набора текста равно $$$$$$ \sum_{i=1}^{n-1} \left|p_{s_i} - p_{s_{i+1}}\right|. $$$$$$

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

Входные данные

В первой строке входных данных находятся целые числа $$$n$$$ и $$$m$$$ — длина текста и количество букв в алфавите ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le m \le 20$$$).

Во второй строке находится строка $$$s$$$ длины $$$n$$$, состоящая из первых $$$m$$$ строчных букв английского алфавита.

Выходные данные

Выведите два целых числа — минимальное и максимальное возможное время набора текста.

Примеры
Входные данные
7 3
abacaba
Выходные данные
6 10
Входные данные
5 1
aaaaa
Выходные данные
0 0
Примечание

В первом примере всего существует $$$6$$$ вариантов назначения позиций для букв «a», «b» и «c»:

  • Если $$$p_{\text{a}} = 1$$$, $$$p_{\text{b}} = 2$$$, $$$p_{\text{c}} = 3$$$: $$$|1 - 2| + |2 - 1| + |1 - 3| + |3 - 1| + |1 - 2| + |2 - 1| = 1 + 1 + 2 + 2 + 1 + 1 = 8$$$.
  • Если $$$p_{\text{a}} = 1$$$, $$$p_{\text{b}} = 3$$$, $$$p_{\text{c}} = 2$$$: $$$|1 - 3| + |3 - 1| + |1 - 2| + |2 - 1| + |1 - 3| + |3 - 1| = 2 + 2 + 1 + 1 + 2 + 2 = 10$$$.
  • Если $$$p_{\text{a}} = 2$$$, $$$p_{\text{b}} = 1$$$, $$$p_{\text{c}} = 3$$$: $$$|2 - 1| + |1 - 2| + |2 - 3| + |3 - 2| + |2 - 1| + |1 - 2| = 1 + 1 + 1 + 1 + 1 + 1 = 6$$$.
  • Если $$$p_{\text{a}} = 2$$$, $$$p_{\text{b}} = 3$$$, $$$p_{\text{c}} = 1$$$: $$$|2 - 3| + |3 - 2| + |2 - 1| + |1 - 2| + |2 - 3| + |3 - 2| = 1 + 1 + 1 + 1 + 1 + 1 = 6$$$.
  • Если $$$p_{\text{a}} = 3$$$, $$$p_{\text{b}} = 1$$$, $$$p_{\text{c}} = 2$$$: $$$|3 - 1| + |1 - 3| + |3 - 2| + |2 - 3| + |3 - 1| + |1 - 3| = 2 + 2 + 1 + 1 + 2 + 2 = 10$$$.
  • Если $$$p_{\text{a}} = 3$$$, $$$p_{\text{b}} = 2$$$, $$$p_{\text{c}} = 1$$$: $$$|3 - 2| + |2 - 3| + |3 - 1| + |1 - 3| + |3 - 2| + |2 - 3| = 1 + 1 + 2 + 2 + 1 + 1 = 8$$$.

Минимальное время набора среди всех раскладок равно $$$6$$$, а максимальное равно $$$10$$$.

Во втором примере существует единственная раскладка $$$p_{\text{a}} = 1$$$ с временем набора $$$0$$$.

F. Стильные комбо
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Саша хочет попасть в киберспортивную команду по своей любимой компьютерной игре. Для этого он отправил запись своего прохождения уровня в этой игре, состоящую из $$$n$$$ последовательных действий. Каждое действие однозначно определяется своим целочисленным идентификатором, поэтому запись представляет собой последовательность целых чисел $$$a_1, a_2, \ldots, a_n$$$.

Непрерывный подотрезок записи $$$a_l, a_{l+1}, \ldots, a_r$$$ ($$$1 \le l \le r \le n$$$) называется стильным комбо, если внутри него игрок ни разу не повторил одно и то же действие — иными словами, все числа $$$a_l, a_{l+1}, \ldots, a_r$$$ попарно различны.

Рекрутерам команды интересны только уникальные стильные комбо. Два стильных комбо $$$a_{l_1}, a_{l_1+1}, \ldots, a_{r_1}$$$ и $$$a_{l_2}, a_{l_2+1}, \ldots, a_{r_2}$$$ считаются одинаковыми, если они имеют равную длину $$$k = r_1 - l_1 + 1 = r_2 - l_2 + 1$$$ и для каждого целого $$$j$$$ от $$$0$$$ до $$$k - 1$$$ выполняется равенство $$$a_{l_1 + j} = a_{l_2 + j}$$$.

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

Входные данные

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

Во второй строке находятся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ — идентификаторы выполненных действий ($$$1 \le a_i \le 10^{18}$$$).

Выходные данные

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

Примеры
Входные данные
5
2 1 2 1 3
Выходные данные
7
Входные данные
4
7 7 7 7
Выходные данные
1
Примечание

В первом примере в записи встречаются семь различных стильных комбо:

  • три комбо из одного действия: $$$[1]$$$, $$$[2]$$$ и $$$[3]$$$;
  • три комбо из двух действий: $$$[2, 1]$$$, $$$[1, 2]$$$ и $$$[1, 3]$$$;
  • одно комбо из трех действий: $$$[2, 1, 3]$$$.
Подотрезки $$$[2, 1, 2]$$$ и $$$[1, 2, 1]$$$ не являются стильными комбо, так как в каждом из них есть повторяющиеся действия.

Во втором примере все действия одинаковы, поэтому единственным стильным комбо является $$$[7]$$$.

G. Очередной шафл
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Александр купил себе новую колоду карт в киоске. Колода, которую он купил, содержит $$$n$$$ карт, на каждой из которых написано целое число от 0 до $$$10^9$$$.

Александр решил перемешивать колоду. Пусть $$$a_i$$$ — значение $$$i$$$-й карты с верха колоды. За одно перемешивание Александр выполняет следующие действия:

  1. Разбивает колоду на несколько непустых кучек, разрезая её между каждой парой соседних карт с одинаковым значением, то есть таких что $$$a_i = a_{i+1}$$$;
  2. Собирает кучки в обратном порядке, сохраняя порядок карт внутри одной кучки.

Если в колоде нет двух лежащих подряд карт с одинаковым значением, то при попытке ее перемешать методом Александра порядок карт в колоде не меняется.

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

Входные данные

Вам необходимо решить задачу для одной или нескольких колод. В первой строке дано одно число $$$t$$$ — количество колод у Александра ($$$1 \le t \le 10^5$$$).

Далее следуют описания $$$t$$$ колод. Описание каждой колоды состоит из двух строк.

В первой строке дано одно число $$$n$$$ — количество карт в колоде ($$$1 \le n \le 2 \cdot 10^5$$$).

Во второй строке дано $$$n$$$ чисел $$$a_1, \ldots, a_n$$$ — исходный порядок карт, считая сверху ($$$0 \le a_i \le 10^9$$$).

Гарантируется, что сумма $$$n$$$ по всем колодам в одном тесте не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждой колоды выведите одно число — минимальное количество перемешиваний, после которого порядок карт в колоде совпадёт с одним из ранее встречавшихся.

Пример
Входные данные
3
5
0 1 1 2 2
5
0 1 2 1 0
4
1 2 2 1
Выходные данные
2
1
2
Примечание

Первая колода в примере для первого перемешивания будет разбита на кучки $$$[0, 1]$$$, $$$[1, 2]$$$, $$$[2]$$$. После объединения кучек в обратном порядке колода будет иметь вид $$$[2, 1, 2, 0, 1]$$$. Теперь в ней нет двух подряд идущих одинаковых карт и после второго перемешивания она не поменяется. Всего выполнено два перемешивания.

Во второй колоде сразу нет одинаковых подряд идущих карт, поэтому она не поменяется после первого же перемешивания.

Третья колода после первого перемешивания имеет вид $$$[2, 1, 1, 2]$$$, а после второго $$$[1, 2, 2, 1]$$$ и совпадает с изначальной.

H. Лучшая перестановка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это интерактивная задача.

На математическом кружке учитель подготовил $$$n$$$ карточек с целыми числами и выложил их в ряд числами вниз. На $$$i$$$-й карточке написано число $$$a_i$$$, но ученики не знают этих чисел. После этого ученики играют с учителем в следующую игру.

У учеников есть $$$n$$$ жетонов с числами от $$$1$$$ до $$$n$$$, каждое число встречается ровно на одном жетоне. Ученики выполняют не более $$$n$$$ ходов. Каждый ход они выбирают перестановку $$$[p_1, p_2, \ldots, p_n]$$$ чисел от $$$1$$$ до $$$n$$$ и кладут жетоны на карточки, жетон с числом $$$p_i$$$ кладется на $$$i$$$-ю карточку. Учитель в ответ сообщает ученикам значение $$$$$$ S(p)=a_1p_1+a_2p_2+\ldots+a_np_n. $$$$$$

Цель учеников — получить максимальную возможную величину $$$S(p)$$$.

Напишите программу, которая будет играть в эту игру за учеников: сделает не более $$$n$$$ запросов и найдёт перестановку, для которой сумма $$$S(p)$$$ наибольшая. Если таких перестановок несколько, можно найти любую.

Протокол взаимодействия

В первой строке дано целое число $$$n$$$ — длина скрытого массива ($$$1 \le n \le 500$$$).

Чтобы сделать запрос, выведите строку следующего вида:

? $$$p_1\ p_2\ \ldots\ p_n$$$
Числа $$$p_1, p_2, \ldots, p_n$$$ должны образовывать перестановку чисел от 1 до $$$n$$$. В ответ проверяющая программа выведет одно целое число — сумму $$$S(p)$$$. Считайте его перед следующим запросом. Всего разрешается сделать не более $$$n$$$ запросов. Гарантируется, что числа $$$a_i$$$ на карточках лежат в диапазоне от $$$-10^9$$$ до $$$10^9$$$.

Когда найдете перестановку с наибольшей возможной суммой, выведите строку следующего вида:

! $$$p_1\ p_2\ \ldots\ p_n$$$
После этого завершите программу. Окончательный ответ не считается запросом; ждать ответа на него не нужно.

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

После вывода каждого запроса и окончательного ответа обязательно сбрасывайте буфер вывода: например, используйте cout « flush или endl в C++, print(..., flush=True) в Python. Один перевод строки без сброса буфера может привести к превышению времени ожидания.

Пример
Входные данные
4

21

10

20

19
Выходные данные

? 3 1 2 4

? 2 4 1 3

? 4 2 3 1

? 1 3 4 2

! 2 1 4 3
Примечание

В примере скрыт массив $$$(2, -1, 4, 2)$$$. В первом запросе выбрана перестановка $$$(3, 1, 2, 4)$$$, поэтому программа отвечает числом $$$2\cdot 3+(-1)\cdot 1+4\cdot 2+2\cdot 4=21$$$.

После четырех запросов выведен ответ $$$(2, 1, 4, 3)$$$. Для него сумма равна $$$2\cdot 2+(-1)\cdot 1+4\cdot 4+2\cdot 3=25$$$. Большую сумму получить нельзя. Перестановка $$$(3, 1, 4, 2)$$$ также является правильным ответом.

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

I. SMS-код
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для банковского приложения потребовалось разработать функциональность автозаполнения SMS-кодов. Когда пользователю приходит сообщение с подтверждением транзакции, система должна автоматически распознать четырехзначный цифровой код, который идет после отдельного слова CODE через пробел.

Входные данные

В единственной строке записан текст SMS-сообщения, состоящий из заглавных латинских букв, цифр и пробелов, длина строки от $$$9$$$ до $$$10^3$$$. Гарантируется, что в сообщении ровно одно вхождение слова CODE, а за ним через пробел записан четырехзначный код.

Выходные данные

Выведите извлечённый четырехзначный код подтверждения.

Примеры
Входные данные
1208 RUB IN EIRC SPB LK CODE 4886
Выходные данные
4886
Входные данные
MYCODE 1234 CODE 0239
Выходные данные
0239
J. Рейтинг таксиста
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Рейтинг на конец дня $$$d$$$ рассчитывается так:

  1. Выбираются поездки за последние $$$X$$$ дней, включая день $$$d$$$.
  2. Если выбранных поездок больше $$$Y$$$, остаются только последние $$$Y$$$ из них. Иначе остаются все выбранные поездки.
  3. Сумма оценок оставшихся поездок делится на их количество. Если не осталось ни одной поездки, рейтинг равен нулю.

Известны дни и оценки $$$n$$$ поездок. Поездки перечислены в порядке совершения, в том числе внутри одного дня. Также даны $$$q$$$ запросов: в каждом указан день, на конец которого нужно узнать рейтинг. Дни запросов перечислены от более ранних к более поздним и могут повторяться.

Для каждого запроса определите рейтинг таксиста после всех поездок указанного дня.

Входные данные

В первой строке находится целое число $$$t$$$ — количество наборов входных данных ($$$1 \le t \le 10^4$$$).

В первой строке каждого набора находятся четыре целых числа: $$$n$$$ — количество поездок, $$$q$$$ — количество запросов, $$$X$$$ — за сколько последних дней учитываются поездки, $$$Y$$$ — максимальное количество поездок в расчете рейтинга ($$$0 \le n \le 2\cdot 10^5$$$; $$$1 \le q, Y \le 2\cdot 10^5$$$; $$$1 \le X \le 10^9$$$).

В каждой из следующих $$$n$$$ строк находятся целые числа $$$d_i$$$ и $$$a_i$$$ — день и оценка $$$i$$$-й поездки ($$$1 \le d_i \le 10^9$$$; $$$1 \le a_i \le 5$$$). Поездки перечислены в порядке совершения: $$$d_1 \le d_2 \le \ldots \le d_n$$$. Порядок строк с одинаковым днем соответствует порядку поездок в этот день.

В каждой из следующих $$$q$$$ строк находится целое число $$$b_j$$$ — день $$$j$$$-го запроса ($$$1 \le b_j \le 10^9$$$). Запросы перечислены в порядке неубывания номера дня: $$$b_1 \le b_2 \le \ldots \le b_q$$$.

Гарантируется, что сумма значений $$$n+q$$$ по всем наборам входных данных не превышает $$$2\cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите ответы на все $$$q$$$ запросов в том же порядке, в котором они даны. Каждый ответ выводите в отдельной строке.

Ответ считается правильным, если его абсолютная или относительная погрешность не превышает $$$10^{-6}$$$. Формально, если ваш ответ равен $$$v$$$, а правильный ответ равен $$$u$$$, должно выполняться неравенство $$$|v-u| \le 10^{-6}\cdot\max(1, |u|)$$$.

Пример
Входные данные
2
6 5 2 3
2 5
2 1
3 4
3 2
3 5
6 1
1
2
3
7
8
0 1 2 3
1
Выходные данные
0.000000000
3.000000000
3.666666667
1.000000000
0.000000000
0.000000000
Примечание

В первом наборе $$$X=2$$$ и $$$Y=3$$$: учитываются не более трех последних поездок за текущий и предыдущий дни.

В конце первого дня поездок еще нет, поэтому рейтинг равен нулю. В конце второго дня учитываются обе поездки этого дня, и рейтинг равен $$$(5+1)/2=3$$$.

В конце третьего дня за последние два дня накопилось пять поездок. Из них выбираются три последние, с оценками четыре, два и пять. Рейтинг равен $$$(4+2+5)/3=11/3$$$.

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

Во втором наборе поездок нет.

K. Ходы с XOR
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ваня узнал про операцию ксор (исключающее или) и теперь нажимает эту кнопку на калькуляторе при каждом удобном случае. На экране пока число $$$a$$$, а Ваня хочет получить $$$b$$$. Правда, калькулятор у него вредный: ксорить он разрешает только с числами от нуля до $$$k$$$ включительно.

За один ход Ваня выбирает целое число $$$x$$$ ($$$0 \le x \le k$$$) и заменяет число $$$a$$$ на экране на $$$a \oplus x$$$. Здесь $$$\oplus$$$ обозначает ксор.

Чтобы вычислить ксор двух неотрицательных целых чисел, запишем их в двоичной системе счисления. Если записи имеют разную длину, дополним более короткую ведущими нулями слева. В каждом разряде результата поставим единицу, если биты двух чисел различаются, и ноль, если совпадают. Например, двоичные записи чисел пять и три — $$$101$$$ и $$$011$$$, поэтому их ксор равен $$$110$$$, то есть шести.

Помогите определить минимальное количество ходов, за которое Ваня может получить число $$$b$$$, либо сообщите, что это невозможно.

Входные данные

В первой строке находится целое число $$$t$$$ — количество наборов входных данных ($$$1 \le t \le 10^4$$$).

Каждая из следующих $$$t$$$ строк содержит три целых числа $$$a$$$, $$$b$$$ и $$$k$$$ ($$$0 \le a, b, k \le 10^9$$$).

Выходные данные

Для каждого набора входных данных выведите одно целое число: минимальное количество ходов, необходимое, чтобы получить из $$$a$$$ число $$$b$$$, или $$$-1$$$, если это невозможно.

Пример
Входные данные
6
5 5 0
5 2 7
0 7 4
0 8 7
3 4 0
8 9 1
Выходные данные
0
1
2
-1
-1
1
Примечание

В первом наборе число $$$a$$$ уже равно $$$b$$$, поэтому ходы не нужны.

Во втором наборе выберем $$$x = 7$$$: $$$5 \oplus 7 = 2$$$.

В третьем наборе достаточно двух ходов: $$$0 \oplus 4 = 4$$$, затем $$$4 \oplus 3 = 7$$$. Одного хода недостаточно, поскольку $$$7 \gt k$$$.

В четвёртом наборе любое допустимое $$$x$$$ меньше восьми, поэтому ни один ход не может изменить бит, соответствующий восьми.

В пятом наборе допустимо только $$$x = 0$$$, что не изменяет $$$a$$$.

В шестом наборе выберем $$$x = 1$$$: $$$8 \oplus 1 = 9$$$.

L. Бесконечная пирамидка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Ряды пирамидки нумеруются снизу вверх, начиная с единицы, а кубики в каждом ряду — слева направо, также начиная с единицы. В первом ряду (основании пирамидки) кубики идут группами чередующихся цветов: сначала идет один красный кубик, затем два синих, далее три красных, четыре синих, и так далее — $$$i$$$-я по счету группа состоит из $$$i$$$ кубиков одного цвета.

Каждый следующий ряд строится поверх предыдущего: для каждого $$$k \ge 1$$$ кубик в $$$n$$$-м ряду ($$$n \ge 2$$$) на $$$k$$$-й позиции ставится ровно посередине над кубиками на позициях $$$k$$$ и $$$k + 1$$$ из $$$(n - 1)$$$-го ряда. Цвет нового кубика выбирается по следующему правилу:

  • если два кубика под ним одного цвета, то на них ставится красный кубик;
  • если два кубика под ним разных цветов, то на них ставится синий кубик.

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

По заданным номерам ряда $$$n$$$ и позиции $$$k$$$ определите цвет соответствующего кубика для каждого запроса.

Входные данные

В первой строке дано целое число $$$q$$$ — количество запросов ($$$1 \le q \le 10^5$$$). В следующих $$$q$$$ строках даны по два числа $$$n$$$ и $$$k$$$ — ряд и номер позиции в ряду кубика, цвет которого нужно узнать ($$$1 \le n \le 10^5$$$; $$$1 \le k \le 10^{18}$$$).

Выходные данные

Для каждого запроса в отдельной строке выведите «R», если кубик на указанной позиции красный, и «B» в противном случае.

Пример
Входные данные
10
1 1
1 2
1 3
1 4
2 1
2 2
2 3
3 1
3 2
4 1
Выходные данные
R
B
B
R
B
R
B
B
B
R
Примечание

На рисунке изображен фрагмент пирамидки из десяти кубиков с основанием на первых четырех кубиках первого ряда:

В первом ряду ($$$n = 1$$$) сначала идет группа из одного красного кубика на позиции $$$1$$$, затем группа из двух синих кубиков на позициях $$$2$$$ и $$$3$$$, после чего начинается группа из трех красных кубиков (на рисунке показан ее первый кубик на позиции $$$4$$$).

Во втором ряду ($$$n = 2$$$):

  • кубик $$$(2, 1)$$$ стоит над кубиками $$$(1, 1)$$$ и $$$(1, 2)$$$ разных цветов, поэтому он синий («B»);
  • кубик $$$(2, 2)$$$ стоит над двумя синими кубиками $$$(1, 2)$$$ и $$$(1, 3)$$$, поэтому он красный («R»);
  • кубик $$$(2, 3)$$$ стоит над кубиками $$$(1, 3)$$$ и $$$(1, 4)$$$ разных цветов, поэтому он синий («B»).

Аналогично определяются цвета кубиков в рядах $$$n = 3$$$ и $$$4$$$.