Задача 1. Разность квадратов ≡

Условие

Вы участвуете в разработке программного модуля для системы символьных вычислений. Модуль будет использоваться для решения специального вида диофантовых уравнений.

По заданному целому неотрицательному целому числу n разрабатываемый модуль должен найти два натуральных числа x и y, для которых выполнено равенство x² − y² = n. Найденные числа не должны превышать 2⁶² − 1.

Требуется написать программу, которая по заданному целому неотрицательному числу n находит натуральные числа x и y, не превышающие 2⁶² − 1, разность квадратов которых равна n.

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

В единственной строке дано одно целое число n (0 ≤ n ≤ 2⁶⁰). Обратите внимание, что заданное во вводе число не помещается в 32-битный тип данных, необходимо использовать 64-битный тип данных (например, long long в C++, int64 в Паскале, long в Java).

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

Если искомые x и y существуют, то необходимо вывести две строки: в первой строке выведите слово Yes, а во второй  — искомые x и y.

Если подходящих пар x и y несколько, можно вывести любую из них, но должно выполняться условие 1 ≤ x, y ≤ 2⁶² − 1.

Если решения нет, в единственной строке необходимо вывести слово No.

Ограничения

0 ≤ n ≤ 2⁶⁰

1 ≤ x, y ≤ 2⁶² − 1

Система оценивания

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

Примеры тестов

3

Yes
2 1

2

No

Задача 2. Превышение скорости ≡

Условие

Превышение скорости является опасным нарушением, значительно увеличивающим вероятность трагических последствий транспортных происшествий. К сожалению контроль скорости с использованием радаров и камер не решает проблему полностью. Притормаживая перед камерами, водители едут со значительным превышением на участках дорог, где контроль не ведётся. С целью предотвращения такого поведения используется назначение штрафа за гарантирование превышение скорости, основанное на времени проезда дороги.

Рассмотрим дорогу, состоящую из n участков, пронумерованных от 1 до n. Длина i-го участка составляет l_i метров. На i-м из участков установлено ограничение по скорости в v_i м/с.

За превышение скорости предусмотрены штрафы. В зависимости от превышения, установлены различные штрафы, величина штрафа вычисляется следующим образом.

Пусть e — максимальное превышение разрешённой скорости в процессе пребывания автомобиля на всей дороге, то есть максимальная разница между скоростью автомобиля и максимальной разрешенной скоростью на участке, где он в этот момент находится. Если превышения скорости не было, то штраф не взимается. В противном случае штраф вычисляется так:

• если 0 < e ≤ a₁, то штраф составляет f₁ денежных единиц
• если a₁ < e ≤ a₂, то штраф составляет f₂ денежных единиц
• …
• если a_m − 2 < e ≤ a_m − 1, то штраф составляет f_m − 1 денежных единиц
• если a_m − 1 < e, то штраф составляет f_m денежных единиц

Таким образом, есть m диапазонов превышения скорости и соответствующие им штрафы.

Автоматическая система назначения штрафов получила данные о q автомобилях. Для удобства пронумеруем их от 1 до q. Известно, что i-й автомобиль заехал на дорогу в момент времени s_i, проехал все n участков, после чего выехал с нее в момент времени t_i. Отсчёт времени будем вести в секундах с открытия дороги.

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

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

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

Первая строка входных данных содержит единственное целое число n — количество участков на дороге.

Вторая строка содержит n целых чисел v_i — ограничения скорости на участках.

Третья строка содержит n целых чисел l_i — длины участков.

Четвертая строка содержит единственное целое число m — количество границ диапазонов превышения скорости.

Пятая строка содержит m − 1 целых чисел a_i — границы диапазонов превышения скорости. Гарантируется, что значения a_i строго возрастают. Обратите внимание, что если m = 1, то пятая строка ввода пустая.

Шестая строка содержит m целых чисел f_i — штрафы за диапазоны превышения скоростей. Гарантируется, что значения f_i возрастают.

Седьмая строка содержит единственное целое число q — количество автомобилей, которые надо обработать.

Каждая из следующих q строк содержит два целых числа s_i и t_i — время заезда на трассу и выезда с неё i-го из рассматриваемых автомобилей .

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

Для каждого из q автомобилей выведите в отдельной строке максимальный штраф, который гарантированно можно выписать этому автомобилю, основываясь только на временах его заезда на дорогу и выезда с нее. Если возможна ситуация, что автомобиль ни разу не превысил разрешённую скорость, следует вывести 0.

Гарантируется, что если время въезда или выезда автомобиля изменить не более чем на 10^− 5, штраф, который можно ему выписать, не изменится.

Ограничения

1 ≤ n ≤ 10

1 ≤ v_i, l_i, a_i, f_i ≤ 10⁹

1 ≤ m, q ≤ 10⁵

1 ≤ s_i < t_i ≤ 10⁹

Система оценивания

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

Примеры тестов

3
10 20 30
400 500 600
6
1 5 10 12 16
100 300 600 800 1000 1500
3
10 100
20 70
45 100

0
800
600

Задача 3. Борьба с рутиной ≡

Условие

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

Рассмотрим работу сотрудника в течение n последовательных рабочих дней. Будем считать, что каждый день сотрудник выполняет ровно один тип заданий, обозначим тип заданий, выполняемый сотрудником в i-й день, целым числом a_i.

Для оценки рутинности работы сотрудника будем использовать следующую характеристику. Зафиксируем целое число d и рассмотрим все отрезки из d подряд идущих рабочих дней. Для каждого такого отрезка найдём количество различных типов заданий, которые работник выполнял на протяжении этих дней, и просуммируем эти значения. Полученную величину обозначим как S_d и будем называть её d-разнообразием. Чем d-разнообразие выше, тем больше различных типов заданий выполнял сотрудник. Профилем вариативности сотрудника будем называть массив значений [S₁, S₂, …, S_n].

Требуется написать программу, которая по заданной последовательности a₁, a₂, …, a_n типов выполняемых сотрудником заданий вычисляет его профиль вариативности.

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

В первой строке находится единственное целое число n  — количество последовательных рабочих дней, которые необходимо проанализировать (1 ≤ n ≤ 2 ⋅ 10⁵).

Во второй строке находится n целых чисел a₁, a₂, …, a_n  — типы заданий, которое выполнял сотрудник (1 ≤ a_i ≤ 10⁹).

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

Выведите n целых чисел: S₁, S₂, …, S_n.

Ограничения

1 ≤ a_i ≤ 10⁹

1 ≤ n ≤ 2 ⋅ 10⁵

Система оценивания

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

Замечание

Рассмотрим, как вычисляются значения S_d в первом примере.

1-разнообразие: необходимо просуммировать количество различных типов заданий, выполняемых сотрудником по всем отрезкам, состоящим из одного дня.

Значение 1-разнообразия равно S₁ = 1 + 1 + 1 + 1 + 1 = 5.

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

Значение 2-разнообразия равно S₂ = 2 + 2 + 2 + 2 = 8.

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

Значение 3-разнообразия равно S₃ = 3 + 3 + 2 = 8.

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

Значение 4-разнообразия равно S₄ = 3 + 3 = 6.

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

Значение 5-разнообразия равно S₅ = 3.

Примеры тестов

5
1 3 2 1 2

5 8 8 6 3 

3
10 10 10

3 2 1 

Задача 4. Олимпиада для роботов ≡

Условие

Жюри чемпионата по скоростному вычислению булевых функций среди роботов готовит задания для участников.

Задание для роботов представляет собой таблицу из m строк и n столбцов, каждая ячейка которой содержит целое число. Обозначим число в i-й строке, j-м столбце таблицы как x_i,j. В каждом столбце значения в ячейках таблицы образую перестановку чисел от 0 до m − 1. Иначе говоря, числа в каждом столбце различны: если i ≠ k, то x_{i, j} ≠ x_{k, j} для всех j, и выполнено условие 0 ≤ x_i,j < m.

Для каждого столбца таблицы задаётся значение порога — целое неотрицательное число z_j от 0 до m. В качестве аргументов булевых функций, которые будут вычислять участники олимпиады, используются значения логических выражений x_i,j < z_j. Значение такого логического выражения равно 1, если неравенство выполнено, иначе оно равно 0.

В процессе соревнования участники вычисляют значения m булевых функций — по одному для каждой строки. Каждая булева функция задаётся в виде бесповторной монотонной линейной программы (БМЛП).

Рассмотрим БМЛП для i-й строки таблицы. Она представляет собой последовательность из n − 1 инструкции, пронумерованных от 1 до n − 1, p-я инструкция задаётся тремя числами: a_p, b_p и op_p. Число op_p принимает два возможных значения: 1 для операции and  — логическое "и", 2 для операции or  — логическое "или". Числа a_p и b_p являются номерами аргументов p-й инструкции, выполнены неравенства 1 ≤ a_p, b_p < n + p.

Рассмотрим массив val[1..2 n − 1], каждое из значений которого равно 0 или 1. Проинициализируем значения val[1]..val[n] с использованием порогов, val[j] = 1, если x_i,j < z_j, иначе val[j] = 0. Значение val[n + p] вычисляется с использованием p-й инструкции.

• Если op_p = 1, то val[n + p] = (val[a_p] and al[b_p]), то есть значение val[n + p] равно 1 если и только если каждое из значений val[a_p] и val[b_p] равно 1.
• Если op_p = 2, то val[n + p] = (val[a_p] or al[b_p]), то есть значение val[n + p] равно 1 если и только если хотя бы одно из значений val[a_p] и val[b_p] равно 1.

При этом программа является бесповторной, а именно все 2 n − 2 значений a_p и b_p для p от 1 до n − 1 различны. Иначе говоря, a_p ≠ b_p, а если p ≠ q, то a_p ≠ a_q, a_p ≠ b_q, b_p ≠ a_q и b_p ≠ b_q.

Результатом исполнения программы является значение val[2 n − 1].

Жюри олимпиады подготовило таблицу x_i,j, выбрало булевы функции для каждой строки и записало их в виде БМЛП. Теперь осталось выбрать значение порога для каждого столбца, чтобы получить задание для олимпиады. Жюри считает задание сбалансированным, если ровно s из m программ для строк таблицы возвращают единицу, а остальные m − s возвращают ноль. Ваша задача — помочь жюри найти подходящие значения порогов.

Требуется написать программу, которая по заданным значениям в ячейках таблицы и БМЛП для строк таблицы определяет такие значения порогов z_j, чтобы значение ровно s из m заданных функций было равно 1. Можно доказать, что при описанных в условии задачи ограничениях требуемые значения порогов всегда можно подобрать.

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

В первой строке входных данных заданы целые числа n, m и s (1 ≤ n ≤ 3 ⋅ 10⁵, 1 ≤ m ≤ 3 ⋅ 10⁵, n ⋅ m ≤ 3 ⋅ 10⁵, 0 ≤ s ≤ m).

Далее следует m блоков по n − 1 строке в каждом, каждый блок задает бесповторную монотонную линейную программу для одной строки таблицы. В каждом блоке p-я строка содержит 3 целых числа: a_p, b_p и op_p (1 ≤ a_p < n + p, 1 ≤ b_p < n + p, гарантируется, что в одном блоке все значения a_p и b_p попарно различны, op_p = 1 или op_p = 2).

Последние m строк задают таблицу, i-я строка содержит n целых чисел, j-е из которых равно x_{i, j} (0 ≤ x_{i, j} ≤ m − 1, в каждом столбце все числа различны, то есть если i ≠ k, то x_{i, j} ≠ x_{k, j} для всех j).

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

Выведите n целых чисел — искомые значения порогов z₁, z₂, …, z_n (0 ≤ z_j ≤ m). Если подходящих вариантов несколько, выведите любой из них.

Ограничения

1 ≤ n ≤ 3 ⋅ 10⁵, 1 ≤ m ≤ 3 ⋅ 10⁵, n ⋅ m ≤ 3 ⋅ 10⁵, 0 ≤ s ≤ m

1 ≤ a_p < n + p, 1 ≤ b_p < n + p, гарантируется, что в одном блоке все значения a_p и b_p попарно различны, op_p = 1 или op_p = 2

1 ≤ t_i ≤ 10⁹, 1 ≤ k_i ≤ 10¹⁸

0 ≤ x_{i, j} ≤ m − 1, в каждом столбце все числа различны, то есть если i ≠ k, то x_{i, j} ≠ x_{k, j} для всех j

Система оценивания

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

Замечание

В примере в таблице три строки, каждой соответствует формула. Необходимо найти четыре порога так, чтобы ровно две формулы возвращали 1, а оставшаяся — 0.

Рассмотрим, как будет вычисляться массив val для первой строки.

Первые четыре значения вычисляются на основе чисел в этой строке и порогов:

• val[1] = (x_1,1 < z₁) = (0 < 0) = 0;
• val[2] = (x_1,2 < z₂) = (1 < 1) = 0;
• val[3] = (x_1,3 < z₃) = (2 < 2) = 0;
• val[4] = (x_1,4 < z₄) = (2 < 3) = 1.

Далее выполняем линейную программу для первой строки:

• val[5] = (val[1] and val[2]) = (0 and 0) = 0;
• val[6] = (val[3] and val[4]) = (0 and 1) = 0;
• val[7] = (val[5] or val[6]) = (0 or 0) = 0.

Таким образом значение булевой функции для первой строки равно 0. Кстати, если эту функцию записать формулой, то получится:

(((x_1,1 < z₁) and (x_1,2 < z₂)) or ((x_1,3 < z₃) and (x_1,4 < z₄))).

Аналогично, булева функция для второй строки равна:

((((x_2,1 < z₁) or (x_2,2 < z₂)) and (x_2,3 < z₃)) or (x_2,4 < z₄)),

а для третьей строки:

(((x_3,1 < z₁) and (x_3,4 < z₄)) or ((x_3,2 < z₂) and (x_3,3 < z₃))).

При подстановке порогов z₁ = 0, z₂ = 1, z₃ = 2, z₄ = 3 получим следующие выражения.

Вторая строка:

((((2 < 0) or (2 < 1)) and (1 < 2)) or (0 < 3)) = (((0 or 1) and 1) or 1) = (0 or 1) = 1,

Третья строка:

(((1 < 0) and (1 < 3)) or ((0 < 1) and (0 < 2))) = ((0 and 0) or (1 and 1)) = (0 or 1) = 1.

Заметим, что это не единственный подходящий набор порогов, также подойдут, например, значения z₁ = 0, z₂ = 0, z₃ = 3, z₄ = 3.

Примеры тестов

4 3 2
1 2 1
3 4 1
5 6 2
1 2 2
3 5 1
4 6 2
1 4 1
2 3 1
5 6 2
0 1 2 2
2 2 1 0
1 0 0 1

0 1 2 3