Какой был слон, какой был слон! Слон полосатый, большой. Характер добрый, нежный. Очень любит рыбий жир...
Весь город на ушах, ночью из Московского зоопарка был похищен редкий слон. Известные братья детективы Колобки уже идут по следу главного подозреваемого — иностранца с табуреткой Карбофоса.
Горилла, обитающая в зоопарке, невольно стала свидетелем похищения. Она утверждает, что похититель играл на индийской флейте гипнотическую мелодию.
Мелодия состоит из $$$n$$$ нот с высотами $$$a_1, a_2, \ldots, a_n$$$. Она называется гипнотической, если высота каждой ноты с номером, кратным $$$k$$$ — чётная. Другими словами, числа $$$a_k, a_{2k}, a_{3k}, \ldots$$$ чётные.
Горилла очень переволновалась, поэтому могла перепутать порядок нот. Помогите братьям Колобкам определить, можно ли переставить ноты, чтобы получить гипнотическую мелодию, или горилла ошиблась и мелодия не могла быть гипнотической.
В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
В первой строке каждого набора даны два целых числа $$$n$$$, $$$k$$$ ($$$1 \le k \le n \le 3 \cdot 10^5$$$) — количество нот и параметр гипнотической мелодии.
Во второй строке каждого набора даны $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — высоты нот, которые запомнила горилла.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^5$$$.
Для каждого набора входных данных выведите «YES», если можно так переставить ноты, чтобы мелодия стала гипнотической, или «NO» в противном случае.
Вы можете выводить «YES» и «NO» в любом регистре (например, строки «yES», «yes» и «Yes» будут распознаны как положительный ответ).
26 31 2 3 4 6 55 21 3 5 7 9
YESNO
В первом наборе данных из примера $$$n = 6$$$, $$$k = 3$$$, исходная мелодия $$$[1, 2, 3, 4, 6, 5]$$$ не является гипнотической: на позициях $$$3$$$ и $$$6$$$ стоят нечётные высоты $$$3$$$ и $$$5$$$. Однако можно переставить ноты, например так: $$$[1, 2, 4, 3, 5, 6]$$$. В этой мелодии высоты нот на позициях $$$3$$$ и $$$6$$$ равны $$$4$$$ и $$$6$$$, оба чётные, значит ответ YES.
Во втором наборе данных из примера $$$n = 5$$$, $$$k = 2$$$, исходная мелодия $$$[1, 3, 5, 7, 9]$$$ состоит только из нечётных высот. Как бы мы ни переставляли ноты, на позициях $$$2$$$ и $$$4$$$ всё равно будут стоять нечётные высоты, поэтому ответ NO.
Ночь — самое время расследовать дело о похищении слона. Взяв лишь старый фонарь с зарядом в $$$M$$$ единиц и шляпы, Шеф и Коллега вышли на «охоту».
Поиски слона начнутся с главной улицы. Детективы идут по ней прямо с самого начала без единой остановки, со скоростью $$$1$$$ метр в секунду и постоянно светят вперёд фонариком, длина луча которого равна $$$H$$$ метров.
На расстояниях $$$b_1, b_2, \ldots, b_n$$$ метров от начала улицы стоят зеваки. Считается, что луч фонаря детективов попадает на $$$i$$$-го зеваку, как только сумма позиции детективов от начала улицы и длины луча фонаря становится не меньше $$$b_i$$$.
В момент попадания луча на зеваку он начинает бежать навстречу детективам с ускорением $$$a$$$ метров на секунду в квадрате. Если в момент столкновения зевака имеет скорость $$$V$$$ метров в секунду, придётся отпугнуть его ультрафиолетовой вспышкой, потратив $$$(V+1)^2$$$ единиц заряда фонаря. Обратите внимание, что в другие моменты заряд фонаря не тратится.
Слона в эту ночь братья детективы не нашли, зато к концу «охоты» у фонарика остался строго положительный заряд.
Найдите максимальную целую положительную длину луча $$$H$$$, при которой к концу «охоты» заряд фонаря останется строго положительным.
В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.
В первой строке каждого набора даны три целых числа $$$n$$$, $$$a$$$, $$$M$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le a \le 2500$$$, $$$3 \cdot n \cdot a \le M \le 2 \cdot 10^{14}$$$) — количество зевак, ускорение зеваки при приближении к детективам и заряд фонаря.
Во второй строке каждого набора даны $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \cdot n \le 10^{18}$$$) — позиции зевак от начала улицы.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$.
Для каждого набора входных данных выведите максимальную подходящую длину луча в метрах.
Гарантируется, что решение существует.
44 1 221 2 3 44 2 502 2 4 75 2 3010 10 10 10 103 3 814 6 7
2314
Рассмотрим первый набор входных данных.
Если $$$H = 2$$$:
Суммарно зеваки снимут $$$3 + 5 + 5 + 5 = 18$$$ единицы заряда, $$$22 - 18 \gt 0$$$.
Если $$$H = 3$$$:
Суммарно зеваки снимут $$$3 + 5 + 7 + 7 = 22$$$ единицы заряда, $$$22 - 22 = 0$$$.
Можно показать, что максимальная подходящая длина луча равна двум.
Если вы дочитали примечание до конца, возможно, вам поможет картинка, иллюстрирующая расстояние между детективами и вторым зевакой в разные моменты времени при $$$H = 3$$$:
Ага, вот: «Особые приметы: очень любит рыбий жир, при звуках флейты... теряет волю».
Коллега и Шеф готовятся к операции по захвату слона. Они уже раздобыли индийскую флейту, а сейчас пытаются усилить запах рыбьего жира. Шефу известно, что органическая структура рыбьего жира состоит из двух деревьев, по $$$n$$$ молекул в каждом. Напомним, что деревом называется связный неориентированный граф без циклов.
Шеф хочет провести ровно одно ребро, соединяющее какую-то молекулу первого дерева с какой-то молекулой второго. Запах усилится, если после добавления такого ребра расстояние между любыми двумя молекулами не превосходит $$$k$$$. Расстояние между молекулами определяется как минимальное количество рёбер, которые надо пройти от одной молекулы до другой.
Помогите Шефу посчитать количество способов провести ребро, чтобы запах рыбьего жира усилился.
В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
В первой строке каждого набора даны два целых числа $$$n$$$, $$$k$$$ ($$$2 \le n \le 10^5, 2 \le k \le 2n$$$) — количество вершин в каждом дереве и максимальное расстояние между молекулами.
В следующих $$$n - 1$$$ строках каждого набора даны пары чисел $$$a_i, b_i$$$ ($$$1 \le a_i, b_i \le n$$$) — рёбра между молекулами в первом дереве.
В следующих $$$n - 1$$$ строках каждого набора даны пары чисел $$$c_i, d_i$$$ ($$$1 \le c_i, d_i \le n$$$) — рёбра между молекулами во втором дереве.
Для каждого набора входных данных гарантируется, что наборы рёбер задают корректные деревья.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.
Выведите количество способов провести ребро, чтобы усилить запах рыбьего жира.
34 41 21 31 42 12 34 33 31 22 33 21 39 68 38 42 13 52 67 69 49 78 38 68 24 88 78 18 59 8
210
Рассмотрим все способы провести ребро, чтобы усилить запах в первом наборе входных данных:
Эй, вы! Покажите мне этот большой слон... gut, gut... ja, ja... и дайте мне большой справка, что этот слон есть принадлежать мне!
У директора сети сувенирных лавок слонов есть $$$n$$$ магазинов с попарно различными координатами $$$(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)$$$ и $$$m$$$ точек закупки с попарно различными координатами $$$(X_1, Y_1), (X_2, Y_2), \ldots, (X_m, Y_m)$$$.
Недавние слухи о краже редкого полосатого слона из Московского зоопарка спровоцировали $$$q$$$ запросов. На каждый запрос у директора появляется/пропадает магазин или появляется/пропадает точка закупки.
Директора интересует максимальное манхэттенское расстояние между открытым магазином и открытой точкой закупки. Другими словами, он хочет узнать максимальное значение $$$|x_i - X_j| + |y_i - Y_j|$$$ по всем парам $$$1 \le i \le n$$$, $$$1 \le j \le m$$$. В случае, если в данный момент времени нет ни одного открытого магазина или точки закупок, надо сообщить «KAPUT».
Помогите директору ответить на запросы в столь непростое время.
В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Далее следует описание наборов.
В первой строке даны целые числа $$$n$$$, $$$m$$$ ($$$1 \le n, m \le 5 \cdot 10^5$$$) — количество магазинов и количество точек закупки.
В следующих $$$n$$$ строках даны целые числа $$$x_i, y_i$$$ ($$$-10^9 \le x_i, y_i \le 10^9$$$) — координаты открытых магазинов. Гарантируется, что никакие два магазина не находятся в одной точке.
В следующих $$$m$$$ строках даны целые числа $$$X_j, Y_j$$$ ($$$-10^9 \le X_j, Y_j \le 10^9$$$) — координаты открытых точек закупки. Гарантируется, что никакие две точки закупки не находятся в одной точке.
В следующей строке дано целое число $$$q$$$ ($$$1 \le q \le 5 \cdot 10^5$$$) — количество запросов.
Запросы бывают двух видов:
Гарантируется, что сумма $$$n$$$ по всем наборам данных не превосходит $$$5 \cdot 10^5$$$. То же самое гарантируется для $$$m$$$. То же самое гарантируется для $$$q$$$.
После каждого обновления выведите максимальное расстояние между магазинами и точками закупки. Если после запроса у директора не открыт ни один магазин или не открыта ни одна точка закупки — выведите вместо максимального расстояния «KAPUT» (без кавычек).
33 30 00 10 21 11 21 332 1 32 1 21 0 123 30 00 10 21 11 21 332 1 12 1 22 1 33 30 00 10 21 11 21 341 0 01 0 11 0 21 0 0
321244KAPUT32KAPUT4
Разберем первый набор входных данных:
Первым запросом точка закупки с координатой $$$(1,3)$$$ закрывается, и максимальное расстояние между действующими магазинами и точками закупки — между $$$(0,0)$$$ и $$$(1,2)$$$, то есть $$$3$$$.
Вторым обновлением точка закупки с координатой $$$(1,2)$$$ закрывается, и максимальное расстояние между действующими магазинами и точками закупки — между $$$(0,0)$$$ и $$$(1,1)$$$, то есть $$$2$$$.
Третьим обновлением открывается магазин $$$(0,12)$$$ и максимальное расстояние между действующими магазинами и точками закупки — между $$$(0,12)$$$ и $$$(1,1)$$$, то есть $$$12$$$.
Иностранный торговец животными Карбофос успел найти покупателя похищенного полосатого слона. Он отправил ему в Германию шифрованное сообщение.
В тот же день братьям детективам доложили о пропаже из столичного музея шифровальной машины «Энигма 43». Шеф уверен, что это не совпадение.
«Энигма 43» всегда генерирует целое число $$$\overline{a_1a_2\ldots a_n}$$$ ($$$0 \le a_i \le 9$$$, $$$a_1 \neq 0$$$) длины $$$n$$$, обладающее особым свойством: ни у каких двух соседних пар цифр не совпадает НОД (наибольший общий делитель). Другими словами, для любой тройки подряд идущих цифр $$$\overline{a_i a_{i+1} a_{i+2}}$$$ верно, что $$$\gcd(a_i, a_{i+1}) \neq \gcd(a_{i+1}, a_{i+2})$$$. Любое число, обладающее таким свойством, может быть сгенерировано. В этой задаче $$$\gcd(0, 0) = 0$$$.
В сообщении могут содержаться важные для следствия данные, но его проблематично восстановить. Коллега предложил воспользоваться полным перебором.
Помогите братьям Колобкам посчитать количество сообщений, которые Карбофос мог отправить с помощью «Энигма 43». Так как ответ может быть большим, посчитайте его по модулю $$$10^9 + 7$$$.
В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 5000$$$) — количество наборов входных данных.
В единственной строке каждого набора дано целое число $$$n$$$ ($$$2 \le n \le 10^{18}$$$) — длина сообщения.
Для каждого набора данных выведите единственное число — количество чисел длины $$$n$$$, которые могли быть сгенерированы Энигмой по модулю $$$10^9 + 7$$$.
6234567
9044326631360172811389296
Для $$$n=3$$$ некоторые числа, которые могли быть сгенерированы Энигмой: $$$124$$$, $$$322$$$, $$$504$$$, $$$661$$$, $$$993$$$