Алгоритмы

Кай работает в лаборатории изучения массивов, он экспериментирует с двумя массивами натуральных чисел: \(A = [a_1, a_2, \ldots, a_n]\) длины \(n\) и \(B = [b_1, b_2, \ldots, b_m]\) длины \(m\).

Эксперимент, который проводит Кай, устроен следующим образом. У каждого из массивов отбрасывается произвольный, возможно пустой, префикс, а также произвольный, возможно пустой, суффикс, таким образом, чтобы оставшиеся части массивов имели равную длину. Обозначим получившиеся массивы как \(A'\) и \(B'\), а их длину как \(k\). Затем Кай суммирует поэлементно получившиеся массивы, итоговый массив Кай обозначает как \(C = [c_1, c_2, \ldots, c_k]\).

Пусть, например, \(n = 5\), \(A = [4, 3, 3, 2, 1]\), \(m = 6\), \(B = [4, 1, 5, 1, 3, 2]\), от массива \(A\) отбрасывается первый и последний элемент, от массива \(B\) три первых. После этого массивы имеют вид \(A' = [3, 3, 2]\), \(B' = [1, 3, 2]\), результат их поэлементного суммирования \(C = [4, 6, 4]\).

Задача Кая заключается в том, чтобы получать такие \(C\), которые являются массивами-палиндромами, то есть если числа на первой и последней позиции совпадают, числа на второй и предпоследней позиции совпадают, и так далее, для всех \(i\) числа на позициях \(i\) и \(k - i + 1\) совпадают.

Помогите Каю понять, какой максимальный по длине массив-палиндром он может получить в результате эксперимента.

Формат входных данных
В первой строке ввода даны два целых числа \(n\) и \(m\) — количество элементов в первом и во втором массиве, соответственно (\(1 \leqslant n, m \leqslant 100\,000\)).

Во второй строке ввода даны \(n\) целых чисел \(a_{i}\) — массив \(A\) (\(1 \leqslant a_i \leqslant 100\)).

В третьей строке ввода даны \(m\) целых чисел \(b_{j}\) — массив \(B\) (\(1 \leqslant b_j \leqslant 100\)).

Формат выходных данных
Выведите единственное целое число — максимальное \(k\), что Кай в результате эксперимента может получить массив-палиндром длины \(k\).

Головоломка состоит из \(n\) треугольников. Чтобы решить головоломку, необходимо выбрать из них четыре треугольника и собрать из них большой треугольник по следующей схеме:

Треугольники не должны пересекаться, в объединении они должны давать треугольник. Ровно по одному из выбранных треугольников должны находиться в углах, а один треугольник должен располагаться в центре.

Треугольники лежат на столе, их можно свободно вращать и двигать, но нельзя зеркально отражать.

Требуется найти все различные наборы из четырех треугольников, из которых можно собрать большой треугольник по указанной схеме. Два набора считаются разными, если существует треугольник, входящий в один, но не входящий в другой.

Формат входных данных
В первой строке дано одно целое число \(t\) — номер теста.

В второй строке дано одно целое число \(n\) — количество треугольников в головоломке (\(4 \le n \le 30\)).

В следующих \(n\) строках дано описание треугольников. Один треугольник описывается координатами трех своих углов, данных в порядке обхода треугольника против часовой стрелки. Все координаты целые и по модулю не превышают \(10^5\). Гарантируется, что треугольники не являются вырожденными. В исходном расположении треугольники могут пересекаться.

Формат выходных данных
В первой строке выведите одно целое число — количество наборов из четырех треугольников, из которых можно собрать большой треугольник по указанной схеме.

В следующих строках выведите наборы. Каждый набор задается номерами треугольников, которые в него входят. Треугольники внутри набора можно выводить в любом порядке. Наборы можно выводить в любом порядке.

Замечание
В первом примере из данных четырех треугольников можно собрать один. При этом треугольники не требуется вращать.

Во втором примере все треугольники имеют одинаковую форму прямоугольного треугольника с длинами катетов равными \(1\). Из любых четырех треугольников можно собрать один.

Даны два целых числа \(x\) и \(y\). Назовем последовательность \(a\) длины \(n\) модообразной, если \(a_1=x\), и для всех \(1 < i \le n\) значение \(a_{i}\) равно либо \(a_{i-1} + y\), либо \(a_{i-1} \bmod y\). Здесь \(x \bmod y\) обозначает остаток от деления \(x\) на \(y\).

Определите, существует ли модообразная последовательность длины \(n\), сумма элементов которой равна \(S\), и если существует, то найдите любую такую последовательность.

Формат входных данных
Первая и единственная строка содержит четыре целых числа \(n\), \(x\), \(y\) и \(S\) (\(1 \le n \le 200\,000\), \(0 \le x \le 200\,000\), \(1 \le y \le 200\,000\), \(0 \le S \le 200\,000\)) — длина последовательности, параметры \(x\) и \(y\), и необходимая сумма элементов последовательности.

Формат выходных данных
Если искомая последовательность существует, выведите в первой строке <<Yes>> (без кавычек). Далее, во второй строке выведите \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) через пробел — элементы последовательности \(a\). Если подходящих последовательностей несколько, выведите любую из них.

Если же последовательность не существует, выведите в единственной строке <<No>>.

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки <<yEs>>, <<yes>>, <<Yes>> и <<YES>> будут приняты как положительный ответ.

Замечание
В первом примере условиям удовлетворяет последовательность \([8, 11, 2, 5, 2]\). Таким образом, \(a_1 = 8 = x\), \(a_2 = 11 = a_1 + 3\), \(a_3 = 2 = a_2 \bmod 3\), \(a_4 = 5 = a_3 + 3\), \(a_5 = 2 = a_4 \bmod 3\).

Во втором примере первый элемент последовательности должен равняться \(5\), поэтому последовательность \([2, 2, 2]\) не подходит.

Далекая страна содержит \(n\) городов, соединенных \(n - 1\) дорогами, при этом из любого города можно добраться до любого другого по дорогам страны.

Известно, что каждый город относится ровно к одной провинции. Город \(v\) относится к провинции \(t_v\). Обратите внимание, что конкретная провинция может являться любым подмножеством городов, и возможно из одного города провинции нельзя добраться до другого этой же провинции, проходя только через города этой провинции. Столицей является город номер \(1\).

Банда разбойников собирается грабить караваны, которые будут идти через города страны. У каждого города есть коэффициент того, насколько удобно в нем грабить. В городе \(v\) он равен \(c_v\).

Вам приходят запросы двух типов:

1. Изменить провинцию, к которой относится город \(v\), на \(t_{new}\)

2. В \(k\) городах с номерами \(a_1, a_2, \ldots, a_k\) появляется по одному каравану, которые идут в столицу (город с номером 1) по кратчайшему пути. Разбойники выбирают один город, который находится в провинции \(t\), после чего грабят все караваны, которые пройдут через этот город. Если разбойники ограбят караваны в городе с номером \(v\), то они получат \(c_v \cdot num_v\), где \(c_v\) — коэффициент города \(v\), а \(num_v\) это количество караванов, проходящих через этот город.

Определите максимальный ущерб, равный количеству награбленного разбойниками, для каждого запроса второго типа. Если в провинции, указанной в запросе, нет ни одного города, то ответ на этот запрос равен \(0\).

Формат входных данных
В первой строке даны два целых числа \(n\) и \(q\) (\(2 \le n \le 200\,000, 1 \le q \le 200\,000\)) — количество городов и количество запросов.

Во второй строке дано \(n - 1\) целое число \(p_2, p_3, \ldots, p_n\) (\(1 \le p_i < i\)), где число \(p_i\) означает, что существует дорога между городами \(i\) и \(p_i\).

В третьей строке дано \(n\) целых чисел \(t_1, t_2, \ldots, t_n\) (\(1 \le t_i \le n\)) — номера провинций у городов.

В четвертой строке дано \(n\) целых чисел \(c_1, c_2, \ldots, c_n\) (\(1 \le c_i \le 10^9\)) — коэффициенты успешности грабежа.

Далее идет \(q\) строк описаний запросов. В начале каждой строки дано одно целое число \(x_i\) (\(1 \le x_i \le 2\)) — тип запроса.

1. Если \(x_i = 1\), то далее идет два целых числа \(v\) и \(t_{new}\) (\(1 \le v, t_{new} \le n\)) — номер города, у которого меняется провинция, и номер его новой провинции.

2. Если \(x_i = 2\), то далее идут целые числа \(t\) и \(k\), и \(k\) целых чисел \(a_1, a_2, \ldots, a_k\) (\(1 \le t, k, a_i \le n\)) — номер провинции, в городе которой можно грабить; количество городов, из которых выходят караваны; и номера городов, из которых входят караваны. Гарантируется, что в одном запросе все \(a_i\) различны. Также гарантируется, что сумма \(k\) по всем запросам второго типа не превышает \(200\,000\).

Формат выходных данных
На каждый запрос второго типа выведите одно число — максимальное число, которое разбойники смогут получить. Если в провинции, указанной в запросе, нет ни одного города, то ответ на этот запрос равен \(0\).

Примечание
В первом запросе караваны идут из городов с номерами \(3\) и \(4\) и нужно ограбить их в городе из третьей провинции. Это те же самые города с номерами \(3\) и \(4\), через каждый из которых пройдет по одному каравану. Поэтому разбойники ограбят караваны в третьем городе и получат \(c_3 \cdot 1 = 10 \cdot 1 = 10\).

Во втором запросе караваны также идут из городов с номерами \(3\) и \(4\), но теперь нужно ограбить их в городе из первой провинции. В первой провинции находятся города \(1\) и \(2\), через каждый из которых пройдет два каравана. Среди них разбойники выбирают город \(2\), потому что \(c_2 > c_1\) и ответ на этот запрос равен \(c_2 \cdot 2 = 3 \cdot 2 = 6\).

В третьем провинция для города \(3\) изменяется на \(1\).

В четвертом запросе караваны снова идут из городов с номерами \(3\) и \(4\), и нужно ограбить караваны в городе из первой провинции. То есть разбойники могут ограбить караваны в одном из городов с номерами \(1, 2\) или \(3\). Через города с номерами \(1\) и \(2\) пройдет два каравана, а через город \(3\) только один. Разбойникам выгодно ограбить караваны в городе \(3\) и получить \(c_3 \cdot 1 = 10 \cdot 1 = 10\).

У Кати есть веревочка длиной \(n\) сантиметров.

Катя \(k\) раз выполняет следующую операцию: выбирает самую длинную веревочку из тех, что у неё есть, и разрезает ее на две веревочки. Катя каждый раз разрезает веревочку на две веревочки примерно равной длины, длина каждой из получившихся веревочек измеряется целым числом сантиметров. А именно: если длина веревочки, которую разрезает Катя, четная и равна \(2u\), то после разрезания получается две веревочки длины \(u\), а если она нечетная и равна \(2v+1\), то после разрезания получаются веревочки длиной \(v\) и \(v+1\).

Когда Катя закончила разрезать веревочку, она разложила получившиеся веревочки в порядке невозрастания длины и хочет ответить на \(q\) запросов: какая длина \(t_i\)-й веревочки в получившемся порядке.

Например, пусть \(n=100\) и \(k=5\). Тогда у Кати последовательно есть наборы веревочек следующей длины: \([100]\), \([50, 50]\), \([50, 25, 25]\), \([25, 25, 25, 25]\), \([25, 25, 25, 13, 12]\), \([25, 25, 13, 13, 12, 12]\).

Формат входных данных
На первой строке ввода дано целое число \(n\) (\(2 \le n \le 10^{18}\)).

На второй строке дано целое число \(k\) (\(1 \le k \le n-1\)).

На третьей строке дано целое число \(q\) (\(1 \le q \le k + 1\), \(1 \le q \le 5000\)).

На четвертой строке даны \(q\) целых чисел \(t_1, t_2, \ldots, t_q\) (\(1 \le t_1 < t_2 < \ldots < t_q \le k + 1\)).

Формат выходных данных
Выведите \(q\) чисел, \(i\)-е из выведенных чисел должно быть равно длине \(t_i\)-й по невозрастанию длине веревочки, которая в итоге есть у Кати.

Дано неориентированное дерево "— связный граф из \(n\) вершин без циклов, и число \(k\). Зафиксируем некоторую вершину \(s\) дерева и назовем ее столицей.

Ориентируем ребра дерева в направлении от столицы. Иными словами, ориентируем ребро \((u, v)\) в направлении \(u \to v\), если при подвешивании дерева за вершину \(s\) вершина \(u\) является родителем вершины \(v\). Заметим, что при таком ориентировании ребер каждая вершина достижима из столицы.

Определим расстояние до вершины \(v\) графа как минимальное количество ребер на пути из \(s\) в \(v\). Назовем доступностью вершины \(s\) максимальное из расстояний до всех вершин.

Разрешается добавить в дерево не более \(k\) дополнительных ориентированных ребер.

Для каждой вершины \(s\) дерева определите, какой минимальной доступности можно достичь, если выбрать вершину \(s\) в качестве столицы.

Обратите внимание, что в некоторых подзадачах требуется вывести ответ только для первой вершины.

Формат входных данных
Первая строка содержит три целых числа \(n\), \(k\) и \(t\) (\(2 \le n \le 2 \cdot 10^5\), \(1 \le k \le n - 1\), \(n \cdot k \le 2 \cdot 10^5\), \(0 \le t \le 1\)) — количество вершин дерева, ограничение на максимальное количество добавленных ребер и число \(t\), равное \(0\), если нужно вывести ответ только для вершины с номером \(1\), и равное \(1\) иначе.

Каждая из следующих \(n - 1\) строк содержит два целых числа \(u_i, v_i\) (\(1 \le u_i, v_i \le n\)) — ребра дерева.

Гарантируется, что заданные ребра образуют дерево.

Формат выходных данных

В случае, если \(t = 0\), выведите единственное целое число: минимальную доступность, которую можно достичь, выбрав вершину с номером \(1\) в качестве столицы, и добавив не более \(k\) дополнительных ориентированных ребер.

В случае, если \(t = 1\), выведите \(n\) чисел: \(i\)-е число равняется минимальной доступности, которую можно достичь, выбрав вершину \(i\) в качестве столицы, и добавив не более \(k\) дополнительных ориентированных ребер.

На рисунке приведены иллюстрации к первому примеру. Пунктирными линиями обозначены добавленные ребра. Для вершин \(1\) и \(2\) минимальная доступность равняется \(1\), а для вершин \(3\), \(4\) и \(5\) минимальная доступность равняется 2.

Множество \(A = \{a_1, a_2, \ldots, a_k\}\) различных натуральных чисел с суммой \(a_1+a_2+\ldots+a_k=n\) называется генератором квадратов, если сумма любых \(k-1\) элементов этого множества является полным квадратом целого числа.

Например, множество \(\{1, 22, 41, 58\}\) является генератором квадратов, так как \(1 + 22 + 41 = 64 = 8^2\), \(1 + 22 + 58 = 81 = 9^2\), \(1 + 41 + 58 = 100 = 10^2\), \(22 + 41 + 58 = 121 = 11^2\).

По заданным \(n\) и \(k\) постройте множество из \(k\) различных натуральных чисел с суммой \(n\), которое является генератором квадратов, либо выясните, что такого нет.

Формат входных данных
На ввод подаются два целых числа \(n\) и \(k\) (\(2 \le n \le 200\,000\), \(2 \le k \le 30\)).

Формат выходных данных
Если искомый генератор квадратов существует, выведите <<YES>> на первой строке, а на второй строке выведите \(k\) натуральных чисел "— искомое множество.

Если генератора квадратов с заданными параметрами не существует, выведите <<NO>>.

Команда исследователей-археологов, отправилась в затерянный храм на поиски древних артефактов. На каждом артефакте записана строка, состоящая из символов "0" и "1". Археологи узнали, что выйти из храма с артефактами можно только в том случае, если суммарное количество нулей в строках, записанных на всех, взятых с собой артефактах, будет не больше m, а суммарное количество единиц не больше n. Исследователи хотят унести как можно больше артефактов. Ваша задача определить, какое максимальное количество артефактов исследователи-археологи смогут унести. 

Входные данные
Первая строка содержит целое число k - количество артефактов в храме. Далее идут k строк si; в i-й строке записана строка с i-го артефакта, состоящая из "0" и "1".
На k+2 строке записаны 2 числа: m и n. 
 

Ограничения

• 1 <= k <= 600
• 1 <= длина si <= 100
• si состоит только из цифр '0' and '1'.
• 1 <= m, n <= 100

Выходные данные
Выведите ответ на задачу.

Пояснения к тестовым примерам
В первом тестовом примере наибольшим подмножеством, содержащим не более пяти 0 и не более трех 1, является {"10", "0001", "1", "0"}, поэтому ответ - 4.
Другие допустимые, но меньшие подмножества  {"0001", "1"} и {"10", "1", "0"}.
Подмножества {"111001"} является недопустимым, так как содержит четыре 1, что больше n.

Магистр Аркадий любит путешествовать на поезде. Он собирается отправиться в множество поездок в течение года и заранее знает, в какие дни он поедет.

Аркадий может купить билеты по разным тарифам:

• 1-дневный тариф стоит C1 рублей;
• 7-дневный тариф стоит C2 рублей;
• 30-дневный тариф стоит C3 рублей.

Каждый билет начинает действовать с того дня, когда был куплен. 
Например, если Аркадий купит 7-дневный билет на 2-й день путешествия, то он  сможет путешествовать 7 дней: 2, 3, 4, 5, 6, 7 и 8 дни.

Помогите Аркадию найти минимальную стоимость, за которую можно купить билет(ы), чтобы он мог отправиться путешествовать в любой из запланированных дней.
 

Ограничения:

• 1 <= n <= 365
• 1 <= daysi <= 365
• Порядковы номера дней daysi даются в строго возрастающем порядке.
• 1 <= С1, С2, С3 <= 1000

Примеры

6
1 4 6 7 8 20
2 7 15

11

12
1 2 3 4 5 6 7 8 9 10 30 31 
2 7 15

17

Ограничения

• n == количество строк в матрице
• m == количество столбцов в матрице
• 1 <= n, m <= 300
• a[i][j] это 0 или 1.

Примеры

4 5
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

4

2 2
0 1 
1 0

1

Юля выписала на доску n последовательных натуральных чисел a, a+1, …, a+n−1 и написала под каждым из них сумму его цифр в десятичной записи, под i-м числом было выписано sumi.

После этого Юра стёр исходные числа и оставил только их суммы цифр. От вас требуется восстановить первое число в исходной последовательности a.
 

В первой строке содержится одно целое число n (2 <= n <= 100000) - длина исходной последовательности.

В следующей строке содержатся n целых чисел sum1, sum2, …, sumn (1 <= sumi <= 90) - суммы цифр чисел исходной последовательности.

Гарантируется, что для всех тестов существует подходящее a, такое что 1 <= a <= 10¹⁸.

В первом тестовом примере сумма цифр 1 равняется 1, сумма цифр 2 равняется 2, сумма цифр 3 равняется 3, что соотносится с массивом sum, поэтому a = 1 подходит под условие задачи.

Во втором тестовом примере сумма цифр 77 равняется 14, сумма цифр 78 равняется 15, сумма цифр 79 равняется 16, сумма цифр 80 равняется 8, сумма цифр 81 равняется 9, что соотносится с массивом sum, поэтому a = 77 подходит под условие задачи.

Примеры

3
1 2 3

1

5
14 15 16 8 9

77

Примеры

Выведите два числа: первое число - номер дня, в который Антон Б. поедет покупать конфеты, второе - номер дня, в который он поедет продавать конфеты. В случае, если таких вариантов дней несколько, выведите любой из них. Если Антон Б. в итоге не сможет получить прибыль ни при каких вариантах, то выведите два нуля.

Примеры

6
10 3 5 3 11 9

2 5 

4
5 5 5 5

0 0

В лесополосе осуществляется посадка деревьев. Причем саженцы высаживают рядами на одинаковом расстоянии.
Через какое-то время осуществляется аэросъемка, в результате которой определяется, какие саженцы прижились. Необходимо определить ряд с максимальным номером, в котором есть подряд не менее 11 неприжившихся саженцев, при условии, что справа и слева от них саженцы прижились.
В ответе запишите сначала наибольший номер ряда, затем наименьший номер из неприжившихся мест.

Входные данные
В первой строке входного файла находится число N - количество прижившихся саженцев (натуральное число, не превышающее 10 000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 100 000: номер ряда и номер места, на котором прижились саженцы.

Выходные данные
Два целых неотрицательных числа: наибольший номер ряда, затем наименьший номер из неприжившихся мест.

Пример входного файла

7
40 30
40 34
50 125
50 129
50 64
50 68
50 70

Ответ для примера (при поиске 3 подряд идущих неприжившихся саженца):
50 65

Файл к заданию