Светозар живёт в самом обычном многоэтажном доме на этаже $$$n$$$. Как и в любом подобном доме в наших краях, вход в дом и выход из него находятся на первом этаже.
Однажды ему понадобилось выйти на улицу, и он решил не пользоваться лифтом, а спуститься по лестнице. Внезапный вопрос «а сколько между двумя этажами ступенек?» привёл любопытного Светозара к тому, что он стал считать ступеньки между этажами. А когда посчитал, то понял, что случайно пошёл вверх и оказался на один этаж выше! Зато теперь он знает, что между каждыми двумя соседними этажами ровно $$$x$$$ ступенек.
Теперь ему нужно спуститься по лестнице с $$$(n + 1)$$$-го этажа на первый этаж. Сколько ещё ступенек придётся пройти Светозару?
Первая строка содержит целое число $$$n$$$ ($$$2 \leqslant n \leqslant 100$$$) — номер этажа, на котором живёт Светозар.
Вторая строка содержит целое число $$$x$$$ ($$$2 \leqslant x \leqslant 100$$$) — количество ступенек между двумя соседними этажами.
Гарантируется, что этаж с номером $$$n$$$ не является последним в доме.
Выведите одно целое число — количество ступенек от этажа $$$n + 1$$$ до первого этажа.
420
80
67
42
В первом примере Светозар поднялся с четвёртого этажа на пятый, и теперь ему нужно спуститься на один этаж 4 раза. Поэтому потребуется пройти $$$80$$$ ступенек.
Светозар, конечно, не выходит на улицу просто так. У него есть очень важные дела в другом районе города. Только как туда добраться? К счастью, в городе, где живёт Светозар, есть метро — да не простое, а с кольцевой линией!
Кольцевая линия состоит из $$$n$$$ станций, последовательно пронумерованных от $$$1$$$ до $$$n$$$ по часовой стрелке. Между любыми двумя соседними станциями существует двусторонний перегон: между станциями $$$1$$$ и $$$2$$$, между $$$2$$$ и $$$3$$$, ..., между $$$n - 1$$$ и $$$n$$$, а также между $$$n$$$ и $$$1$$$. Поезда могут перемещаться в обоих направлениях.
Стоимость проезда по одному перегону между станциями $$$u$$$ и $$$v$$$ зависит от их номеров:
Светозар находится на станции $$$s$$$, а нужно ему на станцию $$$f$$$ ($$$s \ne f$$$). Определите минимальную стоимость такой поездки в монетах, если пользоваться только кольцевой линией метро.
Первая строка содержит целое число $$$t$$$ ($$$1 \leqslant t \leqslant 10^4$$$) — количество тестовых случаев. Далее следуют $$$t$$$ описаний тестовых случаев.
Единственная строка описания содержит три целых числа $$$n$$$, $$$s$$$ и $$$f$$$ ($$$3 \leqslant n \leqslant 10^9$$$, $$$1 \leqslant s, f \leqslant n$$$, $$$s \ne f$$$) — количество станций на линии, начальную и конечную станции поездки.
Для каждого тестового случая выведите в отдельной строке минимальную стоимость поездки со станции $$$s$$$ на станцию $$$f$$$.
85 1 56 1 65 1 46 1 43 1 23 3 16 2 367 60 7
213312115
В примере в первых двух тестовых случаях дешевле всего проехать одну станцию против часовой стрелки. Таким образом, стоимость поездки равна $$$2$$$ монетам в первом случае (поскольку чётности номеров станций одинаковы) и $$$1$$$ монете во втором случае (так как чётности различны).
В третьем случае следует проехать две станции против часовой стрелки за $$$2 + 1 = 3$$$ монеты.
Светозар вышел из метро в совершенно другом, не похожем на его собственный, районе города. Цветастые вывески с большим количеством букв, расположенные повсюду, радовали глаз.
Дорога пешком была долгой. От скуки Светозар начал смотреть на вывески и искать в словах подстроки-палиндромы длины $$$3$$$. И вы тоже скажите, есть ли такой палиндром в вывеске.
Напомним, что подстрока — это непрерывный фрагмент строки. Строка является палиндромом, если она читается одинаково слева направо и справа налево, а её длина — это количество символов в ней. Например, строки aba и aaa — палиндромы длины $$$3$$$, строка abb палиндромом не является, а строка abba является палиндромом, но не длины $$$3$$$.
Первая строка содержит целое число $$$t$$$ ($$$1 \leqslant t \leqslant 2 \cdot 10^5$$$) — количество тестовых случаев. Далее следуют $$$t$$$ описаний тестовых случаев.
Единственная строка описания содержит строку $$$s$$$ ($$$1 \leqslant |s| \leqslant 2 \cdot 10^5$$$) из строчных латинских букв — содержимое вывески.
Гарантируется, что сумма длин строк $$$s$$$ в одном входном файле не превосходит $$$2 \cdot 10^5$$$.
Для каждого тестового случая выведите YES, если в строке $$$s$$$ есть подстрока-палиндром длины $$$3$$$, или NO в противном случае. Выводить слова можно в любом регистре.
7abaabcaaaabbaaaaabcbdd
YESNONONONOYESYES
В примере в пятом тестовом случае строка abba сама является палиндромом, но её подстроки длины $$$3$$$ — abb и bba — палиндромами не являются.
Любимое число Светозара — число $$$n$$$. Любимый цвет — красный. Любимая геометрическая фигура — квадрат. А самое нелюбимое занятие — дизайн логотипов.
Именно поэтому он поручил это вам. Требования к логотипу простые:
Сгенерируйте любой логотип, удовлетворяющий условиям выше.
Первая строка содержит целое число $$$t$$$ ($$$1 \leqslant t \leqslant 10^4$$$) — количество тестовых случаев. Далее следуют $$$t$$$ описаний тестовых случаев.
Единственная строка описания содержит целое число $$$n$$$ ($$$1 \leqslant n \leqslant 10^6$$$) — количество красных квадратов в логотипе.
Гарантируется, что сумма значений $$$n$$$ в одном входном файле не превосходит $$$10^6$$$.
Для каждого тестового случая выведите логотип в следующем формате.
В первой строке выведите целое число $$$m$$$ ($$$1 \leqslant m \leqslant 10^6$$$).
В следующих $$$m$$$ строках выведите логотип: каждая строка должна содержать ровно $$$m$$$ символов '#' (красный квадрат) или '.' (незакрашенный квадрат).
Если подходящих логотипов несколько, выведите любой.
31210
1#2##..4#######.###.....
Светозар — тоже программист, но он пишет код на магических языках программирования.
Сегодня у него в программе есть массив $$$a$$$, состоящий из $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$. Светозар хочет его упорядочить по неубыванию, то есть сделать каждое следующее число в массиве не меньше предыдущего.
Магия языка программирования пока неподвластна Светозару, поэтому он может делать только операции следующего вида: поменять местами два каких-нибудь соседних элемента $$$a_i$$$ и $$$a_{i+1}$$$, но только в том случае, когда их сумма нечётна. Данную операцию можно применять любое (в том числе нулевое) количество раз. Если Светозар попытается поменять другие пары чисел, у него это не получится.
Определите, может ли Светозар упорядочить массив, или его способностей для этого не хватит.
Первая строка входных данных содержит целое число $$$t$$$ ($$$1 \leqslant t \leqslant 2 \cdot 10^5$$$) — количество тестовых случаев. Далее следуют $$$t$$$ описаний тестовых случаев.
Первая строка описания содержит целое число $$$n$$$ ($$$1 \leqslant n \leqslant 2 \cdot 10^5$$$) — длину массива.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_n$$$ ($$$-10^9 \leqslant a_i \leqslant 10^9$$$) — элементы массива.
Гарантируется, что сумма значений $$$n$$$ в одном входном файле не превосходит $$$2 \cdot 10^5$$$.
Для каждого тестового случая выведите в отдельной строке YES, если массив можно сделать неубывающим, или NO в противном случае. Выводить слова можно в любом регистре.
441 6 3 233 1 214252 4 6 8 10
NONOYESYES
34-3 2 -1 41-10000000004-5 -7 0 2
YESYESNO
Рассмотрим второй пример. В первом тестовом случае достаточно поменять два соседних числа $$$2$$$ и $$$-1$$$, чтобы массив оказался упорядоченным.
Во втором тестовом случае массив уже упорядочен, менять ничего не нужно.
В третьем тестовом случае можно показать, что упорядочить массив обменами соседних чисел, соблюдая правила, не удастся.
Светозар часто общается со своими друзьями в мессенджерах. Он не любит опечатки и поэтому решил очищать от них сообщения, которые похожи на смех.
Смех — это непустая строка нечётной длины, в которой чередуются одна фиксированная гласная буква и одна фиксированная согласная буква. Иначе говоря, смех имеет один из двух видов:
Здесь $$$v$$$ — некоторая гласная буква, $$$c$$$ — некоторая согласная буква; обе буквы одни и те же на весь смех. В частности, любая одна буква является смехом. Гласными считаются буквы 'a', 'e', 'i', 'o', 'u'. Все остальные строчные латинские буквы считаются согласными (в том числе буква 'y').
Помогите Светозару с реализацией: для заданной строки $$$s$$$ из строчных латинских букв найдите самую длинную её подпоследовательность, являющуюся смехом. Если таких подпоследовательностей несколько, выведите лексикографически наименьшую.
Первая строка содержит целое число $$$t$$$ ($$$1 \leqslant t \leqslant 2 \cdot 10^5$$$) — количество тестовых случаев. Далее следуют $$$t$$$ описаний тестовых случаев.
Единственная строка описания содержит строку $$$s$$$ ($$$1 \leqslant |s| \leqslant 2 \cdot 10^5$$$) из строчных латинских букв.
Гарантируется, что сумма длин строк $$$s$$$ в одном входном файле не превосходит $$$2 \cdot 10^5$$$.
Для каждого тестового случая выведите одну строку — искомую подпоследовательность. Если подходящих подпоследовательностей максимальной длины несколько, выведите лексикографически наименьшую из них.
7ahahahhahhaajajhazaababayayoklolkek
ahahahahahaaaabayaykkek
В примере в первом тестовом случае подходит подпоследовательность ahahahahaha. В третьем тестовом случае строка ab имеет чётную длину и не является смехом, поэтому ответ — буква 'a'. В пятом тестовом случае буква 'y' согласная, и вся строка yay является смехом.
Напомним, что подпоследовательность получается из строки удалением нуля или более символов без изменения порядка оставшихся. Последовательность $$$x$$$ лексикографически меньше последовательности $$$y$$$, если выполняется одно из двух условий:
У вас есть $$$2n$$$ карточек, на $$$i$$$-й из которых написано целое положительное число $$$a_i$$$. Определите, существует ли такое целое положительное число $$$x$$$, что карточки можно разбить на две группы по $$$n$$$ штук со следующими свойствами:
Если да, найдите любое такое число.
Первая строка содержит целое число $$$t$$$ ($$$1 \leqslant t \leqslant 2 \cdot 10^5$$$) — количество тестовых случаев. Далее следуют $$$t$$$ описаний тестовых случаев.
Первая строка описания содержит целое число $$$n$$$ ($$$1 \leqslant n \leqslant 2 \cdot 10^5$$$).
Вторая строка содержит $$$2n$$$ целых чисел $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_{2n}$$$ ($$$1 \leqslant a_i \leqslant 10^9$$$).
Гарантируется, что сумма значений $$$n$$$ в одном входном файле не превосходит $$$2 \cdot 10^5$$$.
Для каждого тестового случая выведите одно целое число — подходящее значение $$$x$$$.
Если подходящих значений несколько, выведите любое из них.
Если же подходящего значения $$$x$$$ не существует, выведите $$$-1$$$.
512 812 328 2 4 121 6 2 3267 67 67 67
4-12-167
В примере в первом тестовом случае подойдут, например, $$$x = 2$$$, $$$x = 4$$$ и $$$x = 8$$$.
Во втором тестовом случае подходящего значения $$$x$$$ нет.
Это интерактивная задача.
Светозар хочет сыграть с вами в игру. Он загадал маленькую латинскую букву. Вы можете задавать ему вопросы, чтобы её угадать.
За один вопрос вы можете сообщить Светозару строку $$$s$$$ чётной длины $$$2k$$$ из маленьких латинских букв. В ответ он удалит из строки ровно половину символов на своё усмотрение и сообщит вам строку, которая получилась. Единственное требование, которое он соблюдает, звучит так: если загаданная буква встретилась в строке $$$s$$$, то нужно обязательно удалить хотя бы одно её вхождение.
Используйте свой интеллект, чтобы угадать букву! Вы можете задать не более $$$26$$$ вопросов, но если Светозар поймёт, что вы задали заведомо больше вопросов, чем достаточно для угадывания, то вы проиграете.
Чтобы задать очередной вопрос, выведите на отдельной строке строку $$$s$$$ из маленьких латинских букв чётной длины ($$$2 \leqslant |s| \leqslant 700$$$). Затем прочитайте строку длины $$$|s| / 2$$$ — ответ Светозара.
Вы можете задать не более $$$26$$$ вопросов, но если вы зададите заведомо неоптимальное количество вопросов, то ответом будет строка, состоящая из $$$|s| / 2$$$ знаков '-' (дефис). В таком случае программа обязана немедленно завершиться, а решение получит вердикт «Неправильный ответ». Если программа не сделает этого в такой ситуации, то вердикт может быть неопределённым.
Когда буква найдена, выведите строку ! c, где $$$c$$$ — найденная буква, и корректно завершите программу. После ответа ничего читать не нужно.
После каждого вывода, включая ответ, печатайте перевод строки и сбрасывайте буфер выходного потока, чтобы программа отработала корректно и получила правильный вердикт. Для этого можно использовать fflush(stdout) или std::cout.flush() в C++, System.out.flush() в Java, sys.stdout.flush() в Python.
ab
aabb ! a
В примере программа после одного вопроса приняла решение сообщить, что загадана буква 'a', хотя по одному этому ответу на вопрос невозможно однозначно определить, какая из $$$26$$$ букв была загадана.
Пустые строки показаны только для наглядности. Во взаимодействии пустых строк нет.
Светозар завёл себе канал на популярной видеоплатформе. Первое же видео имело огромный успех! В день $$$i$$$ оно получило $$$a_i$$$ лайков, где $$$a_i$$$ — неотрицательное целое число.
К сожалению, после очередной реорганизации веб-интерфейса по просьбам трудящихся платформа перестала отображать количество лайков в основном меню модерации канала. Теперь для получения полной статистики нужно нажимать очень много кнопок, а то и вовсе в поддержку обращаться!
Впрочем, Светозару пока не нужна полная статистика. У него сохранились $$$n$$$ доказательств того, что в конце дня $$$d_j$$$ общее количество лайков равнялось $$$s_j$$$ (для $$$j = 1, 2, \ldots, n$$$). Таким образом, $$$a_1 + a_2 + \ldots + a_{d_j} = s_j$$$.
Светозару интересно, сколько лайков могло быть за $$$T$$$ последовательных дней, если рассматривать только первые $$$d_n$$$ дней. Иными словами, необходимо найти максимальную теоретически возможную сумму $$$a_\ell + a_{\ell+1} + \ldots + a_{\ell+T-1}$$$ при условии $$$1 \leqslant \ell \leqslant d_n - T + 1$$$. Конечно, период из $$$T$$$ дней не обязан начинаться или заканчиваться непосредственно в дни $$$d_1, d_2, \ldots, d_n$$$, для которых данные уже есть.
Первая строка содержит два целых числа $$$n$$$ и $$$T$$$ ($$$1 \leqslant n \leqslant 2 \cdot 10^5$$$, $$$1 \leqslant T \leqslant 10^6$$$) — количество замеров и длина периода.
Следующие $$$n$$$ строк содержат по два целых числа $$$d_j$$$ и $$$s_j$$$ — день замера и общее количество лайков к концу этого дня. Гарантируется, что $$$d_n \geqslant T$$$, что $$$1 \leqslant d_1 \lt d_2 \lt \ldots \lt d_n \leqslant 10^6$$$ и что $$$1 \leqslant s_1 \leqslant s_2 \leqslant \ldots \leqslant s_n \leqslant 10^9$$$.
Выведите одно целое число — максимально возможное количество лайков за $$$T$$$ последовательных дней.
3 22 44 96 12
9
В примере можно взять последовательность $$$(0, 4, 5, 0, 3, 0)$$$. Она согласуется со всеми замерами. За второй и третий дни получено $$$4 + 5 = 9$$$ лайков. Ни за какие два последовательных дня нельзя получить больше лайков.
В магазин товаров тёмной магии привезли новейшую числовую ленту из антиматерии. Лента бесконечна с одной стороны и состоит из клеток, на которых написаны целые неотрицательные числа: в конце написано число $$$0$$$, затем числа $$$1$$$, $$$2$$$, $$$3$$$, $$$\ldots$$$, и так до бесконечности.
Светозару для его исследований позарез нужен непрерывный отрезок $$$[L, R]$$$ такой ленты, да не простой отрезок, а такой, что побитовое исключающее ИЛИ (XOR) всех его чисел в точности равно заданному волшебному числу $$$A$$$.
Магические товары стоят недёшево, поэтому ему требуется найти подходящий отрезок с минимальным $$$R$$$. Вы можете отыскать любое корректное значение $$$L$$$ — всё равно при покупке придётся отрезать кусок ленты до числа $$$R$$$ включительно.
Первая строка содержит целое число $$$t$$$ ($$$1 \leqslant t \leqslant 2 \cdot 10^5$$$) — количество тестовых случаев. Далее следуют $$$t$$$ описаний тестовых случаев.
Единственная строка описания содержит целое число $$$A$$$ ($$$0 \leqslant A \leqslant 10^{18}$$$).
Для каждого тестового случая выведите в отдельной строке два целых числа $$$L$$$ и $$$R$$$ ($$$0 \leqslant L \leqslant R \leqslant 10^{18}$$$) — границы подходящего отрезка. $$$R$$$ должно быть минимально возможным. Если при минимальном $$$R$$$ подходящих значений $$$L$$$ несколько, выведите любое.
Можно показать, что при заданных ограничениях хотя бы одно решение существует.
801234567
0 01 12 21 21 42 46 63 4
Напомним: побитовое исключающее ИЛИ (XOR) двух целых неотрицательных чисел $$$x$$$ и $$$y$$$ — это такое целое неотрицательное число $$$z$$$, в двоичном представлении которого бит равен $$$1$$$, если значения соответствующего бита чисел $$$x$$$ и $$$y$$$ различаются, или $$$0$$$, если совпадают.
В местной картинной галерее появилась новая художественная композиция, все картины которой написаны Светозаром. Композиция состоит из $$$n \cdot m$$$ картин, упорядоченных в виде решётки из $$$n$$$ строк и $$$m$$$ столбцов с картинами. Картина в строке $$$i$$$ и столбце $$$j$$$ имеет высоту $$$h_{i,j}$$$ и ширину $$$w_{i,j}$$$ сантиметров.
Злой маг Arglwyddytywyllwch уже строит планы на эти картины. Каждый день он приходит в галерею и мечтает о том, как композиция окажется в его замке. Замысел таков: он хочет обрезать некоторые картины (то есть уменьшить их высоту и/или ширину, оставляя их прямоугольными) так, чтобы:
Это делается для того, чтобы все картины можно было склеить в одно большое полотно без пробелов. Впрочем, какова художественная ценность такого полотна, план умалчивает.
Разрешается не обрезать картины вообще, если условия уже выполнены. Поворачивать картины и менять их местами нельзя. При этом Arglwyddytywyllwch хочет минимизировать сумму площадей обрезков и интересуется, насколько мало обрезков может быть в принципе.
Каждый день Arglwyddytywyllwch приходит в галерею, и каждый день, по прихоти музы Светозара, одна из картин меняется на другую, самую новую. Найдите минимальную сумму площадей обрезков после каждой замены картины.
Отметим, что картины обрезаются лишь гипотетически, а вот замены картин вполне реальны и применяются последовательно друг за другом.
Первая строка содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$1 \leqslant n, m, k \leqslant 2 \cdot 10^5$$$, $$$n \cdot m \leqslant 2 \cdot 10^5$$$) — размеры композиции в картинах и количество дней.
Следующие $$$n$$$ строк содержат по $$$2m$$$ целых чисел. $$$i$$$-я из них содержит числа $$$h_{i,1}$$$, $$$w_{i,1}$$$, $$$h_{i,2}$$$, $$$w_{i,2}$$$, $$$\ldots$$$, $$$h_{i,m}$$$, $$$w_{i,m}$$$.
Далее следуют $$$k$$$ строк, описывающие замены картин. Каждая замена задаётся четырьмя целыми числами $$$x$$$, $$$y$$$, $$$h$$$, $$$w$$$ ($$$1 \leqslant x \leqslant n$$$, $$$1 \leqslant y \leqslant m$$$) и заменяет картину $$$(x, y)$$$ новой картиной размера $$$h \times w$$$.
Для всех размеров выполняется $$$1 \leqslant h, w \leqslant 10^6$$$.
Для каждой замены картины выведите одно целое число — минимальную суммарную площадь обрезков после этой замены.
2 3 44 5 3 8 3 106 4 5 7 5 101 2 7 62 1 2 101 1 1 12 3 8 20
41 92 127 237
Светозар — действующий чемпион мира по игре «камень, ножницы, бумага». Сегодня проходит турнир претендентов, по итогам которого определится победитель — именно он бросит Светозару вызов в борьбе за следующий титул.
Каждый матч в игре состоит из одного раунда, в котором игроки одновременно выбирают один из трёх вариантов. Как известно, камень побеждает ножницы, ножницы побеждают бумагу, бумага побеждает камень; если же оба игрока показали одно и то же действие, судья бросает монетку, и победителем может стать любой из игроков с вероятностью $$$\frac{1}{2}$$$.
Сетка турнира претендентов — двоичное дерево матчей: претенденты стоят в листьях, а в каждой внутренней вершине играют победители двух её поддеревьев. Светозар в сетке отсутствует, но его будущий матч с победителем турнира претендентов будет проводиться по тем же правилам.
Для целей честного и непредвзятого отбора дерево матчей сбалансировано по высоте, то есть для каждой внутренней вершины высота поддеревьев отличается не больше чем на $$$1$$$.
Эксперты-аналитики из команды Светозара проанализировали все игры текущего сезона, и для каждого претендента известно распределение, с которым он выбирает камень, ножницы и бумагу. Можно считать, что игрок придерживается своего распределения в любом матче независимо от того, кто его соперник.
Светозар хочет узнать, с какой вероятностью он выиграет, если прямо сейчас выберет камень, ножницы или бумагу как действие на матч за титул. Помогите ему найти эти вероятности.
Первая строка содержит целое число $$$t$$$ ($$$1 \leqslant t \leqslant 2 \cdot 10^5$$$) — количество тестовых случаев. Далее следуют $$$t$$$ описаний тестовых случаев.
Первая строка описания содержит целое число $$$n$$$ ($$$1 \leqslant n \lt 2 \cdot 10^5$$$) — количество вершин дерева.
Вторая строка содержит строку $$$s$$$ длины $$$n$$$ из букв 'n' и 'p'. Она описывает вершины дерева турнира при их первом посещении при прямом обходе. Дерево строится по этой строке следующим образом. Создадим дерево с единственной корневой вершиной и пробежимся по символам строки слева направо.
Далее следует по одной строке на каждую букву 'p' в $$$s$$$ (слева направо). Каждая такая строка содержит три целых числа $$$a_i$$$, $$$b_i$$$ и $$$c_i$$$ ($$$0 \leqslant a_i, b_i, c_i \leqslant 100$$$, $$$a_i + b_i + c_i = 100$$$) — вероятности выбора камня, ножниц и бумаги соответствующим претендентом в процентах.
Гарантируется, что в строке $$$s$$$ количество букв 'p' равно количеству букв 'n' плюс один.
Гарантируется, что построенное дерево является сбалансированным по высоте, то есть у каждой вершины высоты её левого и правого поддеревьев отличаются не больше чем на $$$1$$$.
Гарантируется, что сумма значений $$$n$$$ в одном входном файле не превосходит $$$2 \cdot 10^5$$$.
Для каждого тестового случая выведите три целых числа — вероятности того, что Светозар сможет победить того, кто выиграет турнир претендентов, если выберет против него камень, ножницы и бумагу соответственно, по модулю $$$998\,244\,353$$$.
Формально, пусть $$$M = 998\,244\,353$$$. Можно показать, что каждое значение в ответе может быть представлено в виде несократимой дроби $$$P / Q$$$, где $$$P$$$ и $$$Q$$$ — целые числа и $$$Q \not \equiv 0 \pmod{M}$$$. Вместо значения $$$f = P / Q$$$ нужно вывести такое целое число $$$r$$$, что $$$0 \leqslant r \lt M$$$ и $$$r \cdot Q \equiv P \pmod{M}$$$.
41p100 0 03npp100 0 00 100 03npp50 50 050 50 05npnpp67 13 2020 26 5410 11 79
499122177 0 1499122177 0 1249561089 748683265 499122177126346277 983129554 387890700
Ответы на тестовые случаи в декодированном виде:
Даны $$$m$$$ предполагаемых ответов на запросы суммы на отрезке бинарного (то есть состоящего только из нулей и единиц) массива из $$$n$$$ чисел $$$a_1, a_2, \ldots, a_n$$$: каждый ответ $$$(\ell, r, s)$$$ означает, что $$$a_\ell + a_{\ell + 1} + \ldots + a_r = s$$$.
Найдите какой-нибудь бинарный массив, удовлетворяющий всем ответам. Массив не обязательно определяется однозначно; если существует несколько массивов, найдите любой. Ответы на запросы могут противоречить друг другу, тогда необходимо сказать, что искомого массива нет.
Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leqslant n \leqslant 5000$$$, $$$0 \leqslant m \leqslant 2 \cdot 10^5$$$) — количество элементов в массиве и количество результатов запросов суммы.
Следующие $$$m$$$ строк содержат по три целых числа $$$\ell$$$, $$$r$$$, $$$s$$$ ($$$1 \leqslant \ell \leqslant r \leqslant n$$$, $$$0 \leqslant s \leqslant r - \ell + 1$$$), что означает, что сумма на отрезке $$$[\ell, r]$$$ должна быть равна $$$s$$$.
Если подходящего массива не существует, выведите слово NO.
В противном случае выведите в первой строке слово YES, а во второй строке — $$$n$$$ целых чисел, каждое из которых равно $$$0$$$ или $$$1$$$: любой массив, удовлетворяющий всем запросам.
Слова YES и NO можно выводить в любом регистре.
4 21 3 22 4 1
YES 1 0 1 0
5 31 4 12 5 35 5 1
NO
В первом примере также подходит массив $$$(1, 1, 0, 0)$$$.
Во втором примере можно показать, что первые два результата противоречат друг другу, а это значит, что искомого массива нет.
После освобождения Земли Гномов от нечисти Светозар был единогласно избран администратором, которому теперь решать, как лучше организовать защиту от злых магов.
На следующем всеобщем собрании все гномы выстроились в ряд. У гнома с номером $$$i$$$ в ряду на голове надета шапка цвета $$$a_i$$$. Светозар хочет выбрать несколько подряд идущих гномов в Совет Земли Гномов. Но если строго больше половины гномов в Совете будут с шапками одинакового цвета, то у них сформируется абсолютное большинство. К каким последствиям может привести наличие абсолютного большинства, Светозар пока не знает, но заранее этого опасается.
Пока что Светозар лишь размышляет, каких гномов выбрать. Периодически он задаёт вам один из двух типов вопросов:
Первая строка содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \leqslant n, q \leqslant 2 \cdot 10^5$$$) — количество гномов и количество вопросов Светозара.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leqslant a_i \leqslant 10^9$$$) — цвета шапок гномов.
Далее следуют $$$q$$$ вопросов, по одному в строке, в одном из двух форматов, описанных выше:
Для каждого вопроса второго типа выведите одно целое число — цвет абсолютного большинства для заданного набора гномов или $$$-1$$$, если такого цвета нет.
6 101 1 2 3 4 42 1 42 1 32 2 52 5 61 3 12 1 32 3 61 6 12 1 62 4 5
-1 1 -1 4 1 -1 1 -1
После вопросов первого типа цвета шапок гномов будут выглядеть как $$$(1, 1, 1, 3, 4, 4)$$$ и $$$(1, 1, 1, 3, 4, 1)$$$ соответственно.