Костя готовит площадку для командной олимпиады. Каждой команде нужен стол и три табуретки.
К счастью, на складе школы обнаружились столешницы и сидения для табуреток в неограниченном количестве, но ножки школьной мебели часто ломаются, поэтому Костя заказал в мебельной мастерской $$$n$$$ одинаковых ножек для столов и табуреток. У каждого стола должно быть четыре ножки, у каждой табуретки — три ножки.
В командной олимпиаде участвуют три школьника, поэтому каждой команде нужен стол и три табуретки. Костя собирает мебель так:
Костя очень занят сборкой мебели, помогите ему ответить на вопрос, сколько столов и табуреток у него получится собрать.
На первой строке ввода дано число $$$n$$$ ($$$1 \le n \le 10^{18}$$$).
Выведите два целых числа через пробел — количество столов и табуреток соответственно, которое получится собрать у Кости.
3
0 1
18
1 4
В Центральном банке Берляндии клиенты хранят свои деньги и ценности в ячейках в большом сейфе. Чтобы войти в сейф, клиент набирает личный секретный код, который представляет собой $$$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$$$ станет равен новому коду $$$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$$$. Не существует последовательности операций меньшей стоимости, после которой код $$$A$$$ станет равен коду $$$B$$$.
Во втором примере выполнить требуемое преобразование невозможно.
Александр решил построить себе бассейн около дома и попросил дизайнеров подготовить его проект.
Дизайнеры предложили бассейн в форме выпуклого многоугольника с вершинами в точках $$$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$$$. Полученный бассейн изображён на рисунке справа.
В своей старой тетради Ксюша нашла три числа $$$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
Даню назначили главным редактором школьной стенгазеты в ретро-стиле. Для аутентичности Даня решил набирать ее на пишущей машинке. Старую пишущую машинку Дане найти не удалось, поэтому он заказал в онлайн-магазине современную программируемую пишущую машинку.
Клавиатура машинки представляет собой $$$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»:
Минимальное время набора среди всех раскладок равно $$$6$$$, а максимальное равно $$$10$$$.
Во втором примере существует единственная раскладка $$$p_{\text{a}} = 1$$$ с временем набора $$$0$$$.
Саша хочет попасть в киберспортивную команду по своей любимой компьютерной игре. Для этого он отправил запись своего прохождения уровня в этой игре, состоящую из $$$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
В первом примере в записи встречаются семь различных стильных комбо:
Во втором примере все действия одинаковы, поэтому единственным стильным комбо является $$$[7]$$$.
Александр купил себе новую колоду карт в киоске. Колода, которую он купил, содержит $$$n$$$ карт, на каждой из которых написано целое число от 0 до $$$10^9$$$.
Александр решил перемешивать колоду. Пусть $$$a_i$$$ — значение $$$i$$$-й карты с верха колоды. За одно перемешивание Александр выполняет следующие действия:
Если в колоде нет двух лежащих подряд карт с одинаковым значением, то при попытке ее перемешать методом Александра порядок карт в колоде не меняется.
Александр повторяет перемешивания, пока не встретит порядок карт, который уже встречался ранее. Александру стало интересно, сколько раз он перемешает колоду, прежде чем это произойдет. Помогите ему ответить на этот вопрос.
Вам необходимо решить задачу для одной или нескольких колод. В первой строке дано одно число $$$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]$$$ и совпадает с изначальной.
Это интерактивная задача.
На математическом кружке учитель подготовил $$$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$$$).
Чтобы сделать запрос, выведите строку следующего вида:
Когда найдете перестановку с наибольшей возможной суммой, выведите строку следующего вида:
Обязательно завершайте каждую строку переводом строки.
После вывода каждого запроса и окончательного ответа обязательно сбрасывайте буфер вывода: например, используйте 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)$$$ также является правильным ответом.
Пустые строки в таблице помогают показать порядок сообщений. Ваша программа выводит строки из правого столбца и читает ответы из левого.
Для банковского приложения потребовалось разработать функциональность автозаполнения SMS-кодов. Когда пользователю приходит сообщение с подтверждением транзакции, система должна автоматически распознать четырехзначный цифровой код, который идет после отдельного слова CODE через пробел.
В единственной строке записан текст SMS-сообщения, состоящий из заглавных латинских букв, цифр и пробелов, длина строки от $$$9$$$ до $$$10^3$$$. Гарантируется, что в сообщении ровно одно вхождение слова CODE, а за ним через пробел записан четырехзначный код.
Выведите извлечённый четырехзначный код подтверждения.
1208 RUB IN EIRC SPB LK CODE 4886
4886
MYCODE 1234 CODE 0239
0239
После каждой поездки пассажир ставит таксисту целую оценку от одного до пяти. Сервис такси рассчитывает по этим оценкам рейтинг водителя. Чтобы рейтинг отражал его недавнюю работу, старые поездки не учитываются.
Рейтинг на конец дня $$$d$$$ рассчитывается так:
Известны дни и оценки $$$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$$$.
В конце седьмого дня учитываются поездки шестого и седьмого дней. Такая поездка только одна, с оценкой один. В конце восьмого дня учитываются уже седьмой и восьмой дни, в которые поездок не было. Поэтому рейтинг снова равен нулю.
Во втором наборе поездок нет.
Ваня узнал про операцию ксор (исключающее или) и теперь нажимает эту кнопку на калькуляторе при каждом удобном случае. На экране пока число $$$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$$$.
Ваня решил построить бесконечную пирамидку из кубиков красного и синего цвета по особому правилу.
Ряды пирамидки нумеруются снизу вверх, начиная с единицы, а кубики в каждом ряду — слева направо, также начиная с единицы. В первом ряду (основании пирамидки) кубики идут группами чередующихся цветов: сначала идет один красный кубик, затем два синих, далее три красных, четыре синих, и так далее — $$$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$$$):
Аналогично определяются цвета кубиков в рядах $$$n = 3$$$ и $$$4$$$.