Вам дана последовательность $$$a$$$, состоящая из $$$n$$$ натуральных чисел.
За одну операцию вы можете разбить любое число последовательности на два новых натуральных числа. Остальные элементы последовательности не меняются.
Например: $$$a=[3,2,1]$$$, можно разбить $$$a_1=3$$$ на $$$1$$$ и $$$2$$$, получая $$$a=[1,2,2,1]$$$.
Требуется найти минимальное количество операций, необходимое для того, чтобы превратить $$$a$$$ в палиндром. Можно доказать, что это всегда возможно.
Палиндром — это последовательность, которая читается одинаково в обоих направлениях.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит количество наборов входных данных $$$t$$$ ($$$1 \le t \le 10^5$$$). Далее следует описание наборов входных данных.
Первая строка каждого набора данных содержит целое число $$$n$$$ ($$$2\le n \le 3 \cdot 10^{5}$$$).
Вторая строка содержит $$$n$$$ натуральных чисел $$$a_1,a_2,...,a_n$$$ ($$$1 \le a_i \le 10^9$$$).
Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^{5}$$$.
Для каждого набора входных данных выведите минимальное количество операций, необходимое для того, чтобы превратить $$$a$$$ в палиндром.
433 2 121 166 5 4 3 2 188 7 7 1 9 4 2 2
1 0 3 5
В первом наборе входных данных можно использовать следующую операцию: $$$[\underline{3},2,1]\xrightarrow{}[1,2,2,1]$$$.
Во втором наборе входных данных ничего делать не нужно.
В третьем наборе входных данных можно использовать следующие операции:$$$[\underline{6},5,4,3,2,1]\xrightarrow{}[1,\underline{5},5,4,3,2,1] \xrightarrow{}[1,2,3,\underline{5},4,3,2,1] \xrightarrow{}[1,2,3,4,1,4,3,2,1]$$$.
В автобусе сидят $$$n$$$ пассажиров. Автобус застрял в снегу, и теперь им нужно вытолкнуть его оттуда.
Каждый пассажир имеет массу $$$m_i$$$ и силу $$$f_i$$$. Масса пустого автобуса равна $$$w$$$.
Часть пассажиров должна выйти из автобуса и начать толкать его, в то время как все остальные останутся внутри. Автобус можно будет вытолкнуть только в том случае, если суммарная сила толкающих будет больше либо равна суммарной массе автобуса с пассажирами, сидящими внутри.
Так как на улице довольно холодно, требуется минимизировать количество людей, которым нужно будет выйти из автобуса.
Выведите минимальное количество пассажиров, необходимое для того, чтобы вытащить автобус из снега. Если это невозможно, выведите $$$-1$$$.
Первая строка входных данных содержит целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит целые числа $$$n$$$ и $$$w$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le w \le 10^9$$$).
Вторая строка содержит $$$n$$$ целых чисел $$$m_1, m_2, m_3, \dots, m_n$$$ ($$$1 \le m_i \le 10^9$$$).
Третья строка содержит $$$n$$$ целых чисел $$$f_1, f_2, f_3, \dots, f_n$$$ ($$$1 \le f_i \le 10^9$$$).
Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите единственное число — минимальное количество людей, необходимое для того, чтобы вытащить автобус из снега. Если это невозможно, выведите $$$-1$$$.
43 41 1 16 6 63 41 1 13 3 31 1000100106 107 5 1 4 2 83 1 2 7 5 9
1 2 -1 3
Вам дано $$$20$$$ десятичных строк (десятичная строка - это строка, состоящая из символов от 0 до 9), каждая длины $$$k$$$ ($$$k$$$ делится на $$$10$$$).
Вы должны построить десятичную строку длины $$$19k/10$$$ такую, что хотя бы $$$2$$$ заданных строки представлены в ней в качестве подпоследовательностей (не обязательно подряд идущих).
Если такую строку невозможно найти, выведите -1.
В первой строке входных данных находится целое число $$$k$$$ $$$( 1 \le k \le 10^5, k=0 \mod 10)$$$ — длина строк.
Далее будут даны $$$20$$$ десятичных строк длины $$$k$$$, каждая с новой строки.
Если нужную строку невозможно найти, выведите -1. Иначе выведите найденную строку.
1077000166732682666656912557360365043179498140497834429027900951735109518685927577100429078840342474499343949853013049652234838927938172454939472014008517880325170749973594312612530251566485529045810227
6508143179490497834
В ответе к первому тесту можно найти $$$4$$$-ю строку 6508143179490497834 и $$$5$$$-ю строку 6508143179490497834.
Рудракш - школьник. Но он слишком долго спит. Рудракш часто опаздывает в школу. Кроме того, он очень известен среди своих друзей своими знаниями и любовью к простым числам.
Однажды он проснулся и обнаружил, что очень сильно опаздывает в школу, поэтому отметил свою школу и дом на карте города. Мальчик отметил свой дом в координатах $$$(0,0)$$$, а школу в координатах $$$(x,y)$$$, где $$$x$$$ и $$$y$$$ - натуральные числа. По пути к школе он будет делать остановки.
Так как он сильно любит простые числа, то будет выбирать путь таким образом, чтобы Манхэттенское расстояние между двумя соседними остановками было простым числом. Более формально, он может начать в координатах $$$(a,b)$$$ и закончить в $$$(c,d)$$$ только тогда, когда $$$|a-c|+|b-d|$$$ - простое число. Рудракш хочет дойти до школы, минимизировав количество остановок, сделанных на его пути. Найдите минимальное возможное количество остановок и их координаты.
Он не должен выходить за границы города, то есть в любой момент его x-координата должна быть между $$$0$$$ и $$$x$$$ (включительно), а y-координата должна быть между $$$0$$$ и $$$y$$$ (включительно)
Первая строка входных данных содержит целое число $$$t$$$ $$$(1 \leq t \leq 10^5)$$$ — количество наборов входных данных.
Каждый набор входных данных описывается двумя целыми числами $$$x$$$ $$$(1 \leq x \leq 10^7)$$$ и $$$y$$$ $$$(1 \leq y \leq 10^7)$$$ — координатами школы.
Сумма $$$(x+y)$$$ по всем наборам входных данных будет меньше либо равна $$$10^7$$$.
Для каждого набора входных данных:
Сначала выведите целое число $$$n$$$ - минимальное количество остановок.
Потом выведите $$$n$$$ строк, на каждой по два неотрицательных целых числа $$$x_i$$$ $$$(0 \leq x_i \leq x)$$$ и $$$y_i$$$ $$$(0 \leq y_i \leq y)$$$ — координаты $$$i$$$-й остановки, сделанной Рудракшем.
Для каждого $$$i$$$ $$$(1 \le i \lt n)$$$, $$$|x_{i+1}-x_i| + |y_{i+1}-y_i|$$$ должно быть простым числом. Кроме того, $$$x_1+y_1$$$ тоже должно быть простым числом.
Последняя остановка должна находится в координатах школы. $$$(0,0)$$$ выводить не требуется.
Если существует несколько возможных вариантов ответа, выведите любой из них.
31 12 105 5
1 1 1 2 0 5 2 10 2 3 0 5 5
Дана перестановка $$$a$$$ длины $$$n$$$ и целое число $$$k$$$ $$$(k \le 10)$$$.
Для каждого индекса $$$i$$$ в перестановке, найдите длину наидлиннейшего последовательного подотрезка (длина подотрезка должна быть хотя бы $$$k$$$), содержащего индекс $$$i$$$, такого, что $$$a_i$$$ больше либо равно $$$k$$$-му максимальному элементу на подотрезке. Другими словами, $$$a_i$$$ должно находиться на $$$x$$$-й позиции $$$(x\le k)$$$, когда подмассив отсортирован в убывающем порядке.
Первая строка содержит целое число $$$t$$$ $$$(1 \le t \le 10^5)$$$ - количество наборов входных данных.
Далее следуют описания наборов.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$ и $$$k$$$ $$$(1 \le k \le \min(n,10) )$$$ - размер массива и значение $$$k$$$.
Вторая строка содержит $$$n$$$ положительных чисел $$$a_1, a_2, a_3, ..., a_n$$$ $$$(1 \le a_i \le n)$$$ - элементы $$$a$$$.
Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных, выведите $$$n$$$ положительных чисел, где $$$i$$$-е число равно длине наидлиннейшего подходящего подотрезка для $$$i$$$-го индекса массива.
52 21 24 42 1 4 34 41 2 4 33 23 1 27 41 5 3 4 7 6 2
2 2 4 4 4 4 4 4 4 4 3 2 3 4 7 5 7 7 7 4
Дан массив $$$A$$$ из $$$N$$$ целых чисел. Требуется выбрать $$$K$$$ непустых подпоследовательностей (символы необязательно подряд идущие). Счёт подпоследовательности равен её $$$\rm{mex}$$$ (mex — это минимальное неотрицательное целое число, не встречающееся в последовательности).
Выберите любые $$$K$$$ различных непустых подпоследовательностей и разместите их счёты в любом порядке, после чего добавьте счёты с нечётными индексами к $$$y$$$ и вычтите счёты с чётными индексами из $$$y$$$ (изначально $$$y=0$$$). Более формально: Пусть $$$S$$$ — последовательность счётов, тогда $$$y=S_1-S_2+S_3-\dots-(-1)^K S_K$$$.
Найдите минимальное возможное значение $$$y$$$.
Две подпоследовательности различны в том случае, если существует такой индекс $$$i$$$, что в одной из подпоследовательностей $$$i$$$-й элемент присутствует, а в другой нет. (Таким образом существует $$$2^N-1$$$ непустых подпоследовательностей.)
Первая строка входных данных содержит целое число $$$T$$$ ($$$1 \le T \le 100000$$$) - количество наборов входных данных
Каждый набор состоит из 2 строк:
Первая строка содержит два целых числа $$$N$$$ ($$$1 \le N \le 100000$$$) и $$$K$$$($$$1 \le K \le \min(10^9,2^N - 1)$$$ — размер массива и количество подпоследовательностей, которых нужно выбрать.
Вторая строка содержит $$$N$$$ целых чисел массива $$$A$$$. Для каждого $$$i$$$, $$$0 \le A_i \le 10^9$$$.
Гарантируется, что сумма $$$N$$$ по наборам входных данных не превышает $$$100000$$$.
Для каждого набора входных данных нужно вывести одно целое число — минимальное возможное значение $$$y$$$, которое можно получить.
36 40 0 2 3 1 48 71 2 3 0 1 2 4 63 11 5 2
-10 -15 0
Вам дана строка $$$s$$$ длины $$$n$$$. Вы выполняете следующие операции $$$k$$$ раз:
Найдите лексикографически минимальную строку, которую вы можете получить.
Первая строка входных данных содержит единственное целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$).
Во второй строке содержится строка $$$s$$$, состоящая из $$$n$$$ строчных латинских букв.
Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите лексикографически минимальную строку, которую вы можете получить.
47 3abacaba9 2theforces5 4edcba7 3pavlekn
aaaacbb cheforest abcde aeplknv
В первом примере, мы можем проделать следующие операции:
Во втором примере, мы можем проделать следующие операции: