Известному морскому капитану Христофору Бонифатьевичу Врунгелю прислали приглашение поучаствовать в престижной международной кругосветной парусной регате. Для участия необходима яхта, сборку которой капитан поручил своему ученику Лому.
Палуба однопарусной яхты должна состоять из $$$n$$$ досок, выложенных в ряд. Обозначим количество сучков в $$$i$$$-й доске числом $$$a_i$$$. Палуба называется надёжной, если все подотрезки длины $$$k$$$ её досок содержат ровно $$$k$$$ различных количеств сучков. Другими словами, числа $$$a_1, a_2, \ldots, a_k$$$ должны быть попарно различны, числа $$$a_2, a_3, \ldots, a_{k+1}$$$ должны быть попарно различны, и так далее.
Лом занят изготовлением паруса, поэтому вам придётся помочь ему с палубой. Найдите любой массив количеств сучков $$$a_1, a_2, \ldots, a_n$$$, образующий надёжную палубу.
В первой строке входных данных дано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
В первой строке каждого набора даны целые числа $$$n$$$, $$$k$$$ ($$$1 \le k \le n \le 10^5$$$) — количество досок в палубе и параметр надёжности.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$), образующих надёжную палубу.
Если ответов несколько, вы можете вывести любой.
Можно показать, что ответ всегда существует.
45 15 55 27 3
1 1 1 1 1 2 5 4 1 3 2 1 2 1 2 7 5 1 3 2 5 7
Талантливый картёжник Фукс, работающий охранником в Королевском музее искусств, решает встать на дорогу криминала. Мафиозный Шеф поручает Фуксу похитить скульптуру Венеры Милосской, спрятав её в футляре от контрабаса. Фуксу известно о сигнализации, которую необходимо отключить, чтобы похищение прошло тихо.
На панели управления сигнализацией расположены массив из $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ и массив из $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$. Паролем является количество пар индексов $$$(i, j)$$$ ($$$1 \le i, j \le n$$$), таких что $$$a_i \oplus b_j = k$$$ и $$$a_j \oplus b_i = m$$$. Операция $$$\oplus$$$ обозначает побитовое исключающее ИЛИ. Обратите внимание, что пары $$$(i, j)$$$ и $$$(j, i)$$$ ($$$1 \le i \lt j \le n$$$) считаются различными.
Фукс по характеру неуверенный и боится действовать самостоятельно. Помогите ему определить пароль от панели управления сигнализацией.
В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.
В первой строке каждого набора даны три целых числа $$$n$$$, $$$k$$$, $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le k, m \le 2^{31} - 1$$$) — длина массивов и параметры пароля.
Во второй строке каждого набора даны $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 2^{31} - 1$$$) — первый массив.
В третьей строке каждого набора даны $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \le b_i \le 2^{31} - 1$$$) — второй массив.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$.
Для каждого набора входных данных выведите единственное число — количество подходящих пар индексов.
45 3 47 2 8 1 51 2 3 5 44 0 02 2 3 32 2 3 35 6 07 3 9 1 33 1 2 2 13 3 41 2 35 6 7
1820
В первом наборе входных данных подходит пара индексов $$$(1, 5)$$$ ($$$a_1 \oplus b_5 = 7 \oplus 4 = 3$$$, $$$a_5 \oplus b_1 = 5 \oplus 1 = 4$$$). Можно показать, что другие пары индексов не подходят, значит паролем является число $$$1$$$.
Регата стартовала, и кругосветная гонка в самом разгаре. Экипаж «Беды», состоящий из капитана Врунгеля, студента Лома и шулера Фукса, настроен на победу. В зоне видимости экипажа находятся $$$n$$$ островов. Из-за розы ветров и подводных течений количество фарватеров (прямых маршрутов между островами) ограничено. Капитан обнаружил $$$m$$$ направленных фарватеров, $$$j$$$-й фарватер позволяет добраться с острова $$$v_j$$$ на остров $$$u_j$$$ и имеет длину $$$w_j$$$.
Некоторые фарватеры находятся в зоне мёртвого штиля. После каждого перемещения «Беды» направление такого фарватера меняется на противоположное. Например, если фарватер $$$2 \to 4$$$ длины $$$1$$$ находится в зоне мёртвого штиля, после первого перемещения «Беды» по любому фарватеру он превратится в фарватер $$$4 \to 2$$$ длины $$$1$$$, после второго — в фарватер $$$2 \to 4$$$ длины $$$1$$$, и так далее.
Останавливаться на островах необходимо для пополнения запасов. Помогите капитану Врунгелю найти кратчайшее расстояние от острова $$$1$$$ до всех остальных. Расстояние считается как сумма длин пройденных фарватеров.
В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.
В первой строке каждого набора даны два целых числа $$$n$$$, $$$m$$$ ($$$2 \le n \le 10^5, 1 \le m \le 2\cdot10^5$$$) — количество островов и количество фарватеров.
Во второй строке каждого набора дана строка $$$s$$$ длины $$$m$$$, состоящая из нулей и единиц. Если $$$s_j = 1$$$, то $$$j$$$-й фарватер находится в зоне мертвого штиля, в противном случае — нет.
В следующих $$$m$$$ строках каждого набора даны целые числа $$$v_j$$$, $$$u_j$$$, $$$w_j$$$ ($$$1 \le v_j, u_j \le n$$$, $$$1 \le w_j \le 10^6$$$) — описание фарватеров.
Обратите внимание, что между одной парой островов может быть несколько фарватеров. Кроме того, возможны фарватеры из острова в него же.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$. Также гарантируется, что сумма $$$m$$$ по всем наборам входных данных не превосходит $$$4 \cdot 10^5$$$.
Для каждого набора входных данных выведите $$$n$$$ целых чисел — кратчайшие расстояния от острова номер $$$1$$$ до островов $$$1, 2, \ldots, n$$$. Если невозможно добраться до какого-то острова, вместо расстояния до него выведите $$$-1$$$.
34 400011 2 31 3 53 2 62 4 14 5001011 2 22 3 44 3 53 2 12 4 23 2011 2 12 3 2
0 3 5 120 2 6 -10 1 -1
Экипаж «Беды» сделал остановку в Египте. Гангстеры Джулико Бандитто и Де Ля Воро Гангстеритто планируют перехватить футляр со скульптурой в древней пирамиде. За ними охотится суперагент 00X.
Суперагент детально изучил особенности архитектуры древних пирамид и готов вычислить местоположение гангстеров с помощью эхолокации. Для этого он отправит последовательность ультразвуковых сигналов разной частоты.
Назовём частоту $$$b$$$ следующей за частотой $$$a$$$, если $$$b$$$ — минимальное целое число, большее $$$a$$$, такое что $$$\varphi(a) \lt \varphi(b)$$$. Другими словами, $$$b = \displaystyle\min_{x \in \mathbb{N}}\left(x : \begin{cases}a \lt x \\ \varphi(a) \lt \varphi(x)\end{cases}\right) $$$. Напомним, что $$$\varphi(n)$$$ обозначает значение функции Эйлера от $$$n$$$.
В Египте разрешены только частоты, не меньшие $$$l$$$ и не большие $$$r$$$. Помогите суперагенту определить максимальную возможную длину $$$k$$$ последовательности целых чисел $$$a_1, a_2, \ldots, a_k$$$ ($$$l \le a_i \le r$$$, частота $$$a_{i+1}$$$ является следующей для $$$a_i$$$).
В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 5 \cdot 10^5$$$) — количество наборов входных данных.
В каждом наборе входных данных даны целые числа $$$l$$$, $$$r$$$ ($$$1 \le l \le r \le 10^6$$$) — подотрезок разрешённых частот в Египте.
Обратите внимание, что ограничений на сумму $$$r - l$$$ по всем наборам входных данных нет.
Для каждого набора входных данных выведите единственное целое число $$$k$$$ — максимальную длину подходящей последовательности.
614 181 207 172 271 79177 190
385144
Миновав множество опасностей и потеряв студента Лома, экипаж «Беды» прибывает на Гавайи. Предприимчивый директор театра принимает путешественников за артистов и просит выступить в местном театре.
В гримёрке в ряд расположены $$$n$$$ чехлов от контрабасов с высотами $$$a_1, a_2, \ldots, a_n$$$. Несчастный Фукс забыл, какой из чехлов принадлежит ему, поэтому просит вашей помощи.
Назовём схожестью двух мультимножеств количество элементов в их пересечении, например, схожесть мультимножеств $$$\{1, 4, 4, 5\}$$$ и $$$\{2, 4, 5, 7, 11\}$$$ равна $$$2$$$ (пересечение $$$\{4, 5\}$$$), а схожесть мультимножеств $$$\{3, 3, 3\}$$$ и $$$\{1, 3, 3, 3, 4\}$$$ равна $$$3$$$ (пересечение $$$\{3, 3, 3\}$$$). Обратите внимание, что порядок элементов в мультимножестве не имеет значения.
Вам предстоит ответить на $$$q$$$ запросов. Каждый запрос задаёт подотрезок чехлов $$$a_l, a_{l+1}, \ldots, a_r$$$. Вы можете выбрать любое целое число $$$k$$$ ($$$l \le k \le r$$$), чтобы схожесть подотрезка $$$a_l, a_{l+1}, \ldots, a_k$$$ и подотрезка $$$a_{k+1}, \ldots, a_r$$$ была максимальной. Найдите максимальную возможную схожесть.
Вы не понимаете, как такие странные запросы помогут Фуксу с поиском своего чехла, но соглашаетесь помочь.
В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
В первой строке каждого набора дано целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — количество чехлов от контрабасов.
Во второй строке каждого набора даны $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — высоты чехлов.
В третьей строке каждого набора дано целое число $$$q$$$ ($$$1 \leq q \leq 10^5$$$) — количество запросов.
В следующих $$$q$$$ строках даны целые числа $$$l$$$ и $$$r$$$ ($$$1 \leq l \leq r \leq n$$$) — запросы поиска максимальной схожести.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$. То же самое гарантируется для $$$q$$$.
Для каждого набора входных данных выведите $$$q$$$ целых чисел — ответы на соответствующие запросы.
281 2 1 3 2 1 2 351 82 73 64 81 494 3 3 3 4 3 1 3 332 91 53 7
3 2 1 2 13 2 1