Задача 1. Новый год в детском саду ≡

Условие

В детском саду готовятся к новому году, и воспитательница !A !B !C решила организовать детей, чтобы они подготовили украшения и отправили их Санте Клаусу для украшения своих оленей.

Дети с интересом восприняли идею и вырезали из бумаги a звездочек и b снежинок. Теперь они планируют отправить их Санте Клаусу по почте. Им так понравились вырезанные ими украшения, что они, возможно, решат оставить себе часть. Таким образом, дети могут отправить Санте x звездочек и y снежинок, где 0 ≤ x ≤ a и 0 ≤ y ≤ b. Чтобы Санта не расстроился, дети должны отправить ему хотя бы одно украшение. То есть должно выполняться также условие x + y > 0.

Чтобы все олени выглядели красиво, на каждом должно оказаться одинаковое количество украшений. Известно, что у Санты n оленей, поэтому если будут отправлены x звездочек и y снежинок, величина x + y должна делиться на n.

Воспитательница заинтересовалась: а сколько есть всего различных способов составить посылку Санте Клаусу. Два способа считаются различными, если в них отличается количество звездочек или количество снежинок.

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

В одном наборе входных данных содержатся несколько тестов. Каждый тест следует решить независимо.

Первая строка входных данных содержит целое число t — количество тестов (1 ≤ t ≤ 10⁵).

Следующие строки описывают тесты, по одному на строке. Описание теста состоит из трех целых чисел n, a и b — количество оленей у Санты, количество звездочек и количество снежинок, вырезанных детьми (4 ≤ n ≤ 10⁹; 0 ≤ a, b ≤ 10⁹).

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

Выведите t чисел. Для каждого теста выведите одно число: количество способов составить посылку для Санты Клауса.

Ограничения

1 ≤ t ≤ 10⁵

4 ≤ n ≤ 10⁹; 0 ≤ a, b ≤ 10⁹

Система оценки

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

Замечание

В первом тесте у Санты 4 оленя, а дети вырезали 2 звездочки и 2 снежинки. Здесь подходит только один набор — нужно отправить все вырезанные украшения.

Во втором тесте у Санты также 4 оленя, но дети вырезали 4 звездочки и 4 снежинки. Здесь подходит 6 наборов: 0 звездочек и 4 снежинки, 1 звездочка и 3 снежинки, 2 звездочки и 2 снежинки, 3 звездочки и 1 снежинка, 4 звездочки и 0 снежинок, а также 4 звездочки и 4 снежинки.

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

4
4 2 2
4 4 4
6 5 5
8 13 17

1
6
5
30

Задача 2. Сортировка дробей ≡

Условие

На доске выписано две последовательности из n различных целых чисел: A = [a₁, a₂, …, a_n] и B = [b₁, b₂, …, b_n].

Составим из них n² дробей вида a_i / b_j, сократим каждую дробь и отсортируем их по неубыванию.

Задано число q и q целых чисел c₁, c₂, …, c_q. Для каждого j следует выдать c_j-ю в неубывающем порядке дробь из получившихся.

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

На первой строке ввода находятся числа n и q (1 ≤ n ≤ 10⁵, 1 ≤ q ≤ 10⁵, q ≤ n²).

Дополнительно выполняется неравенство n ⋅ q ≤ 10⁵.

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

На третьей строке ввода находятся n различных целых чисел b₁, b₂, …, b_n (1 ≤ b_i ≤ 10⁶).

На четвертой строке ввода находятся q различных целых чисел c₁, c₂, …, c_q (1 ≤ c_i ≤ n²).

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

Выведите q строк. На j-й строке выведите c_j-ю по неубыванию дробь среди получившихся. Дробь p / q следует выводить в формате {p q}, дробь должна быть несократимой.

Ограничения

1 ≤ n ≤ 10⁵, 1 ≤ q ≤ 10⁵, q ≤ n²

n ⋅ q ≤ 10⁵

1 ≤ a_i ≤ 10⁶

1 ≤ b_i ≤ 10⁶

1 ≤ c_i ≤ n²

Система оценки

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

Пояснение к примеру

В примере дроби исходно равны:

[32, 33, 34, 35, 42, 43, 44, 45, 12, 13, 14, 15, 22, 23, 24, 25],

после сокращения

[32, 11, 34, 35, 21, 43, 11, 45, 12, 13, 14, 15, 11, 23, 12, 25],

после сортировки

[15, 14, 13, 25, 12, 12, 35, 23, 34, 45, 11, 11, 11, 43, 32, 21].

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

4 8
3 4 1 2
2 3 4 5
1 16 2 4 5 6 10 15

1 5
2 1
1 4
2 5
1 2
1 2
4 5
3 2

Задача 3. Оптические каналы связи ≡

Условие

Всего во Флатландии n городов, пронумерованных от 1 до n, столица Флатландии имеет номер 1. Компьютерная сеть Флатландии устроена следующим образом: в каждом городе есть один центр подключения, который может быть связан с некоторыми другими центрами с помощью проводных каналов связи. При этом между любыми двумя городами есть ровно один маршрут по каналам связи, иначе говоря, сеть представляет собой дерево. Для города i, где i > 1, обозначим первый город на маршруте от города i до столицы как p_i.

Запланирована модернизация сети Флатландии, в результате которой некоторые каналы связи будут заменены на более современные оптические. Оптические каналы могут быть проложены только вместо существующих проводных. Стоимость замены канала, который соединяет город i с городом p_i, равна w_i. Из-за ограничений технологии любой центр подключения может быть непосредственно подключен оптическими каналами не более чем к k другим центрам.

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

Помогите специалистам министерства выбрать каналы для модернизации.

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

На первой строке ввода находятся два целых числа n и k (2 ≤ n ≤ 10⁵, 1 ≤ k ≤ 100).

На следующих n − 1 строках заданы описания каналов, (i − 1)-я из этих строк содержит два целых числа: p_i и w_i (1 ≤ p_i ≤ i, 0 ≤ w_i ≤ 10⁹).

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

Выведите два целых числа cnt и cost: максимальное число каналов, которое удастся модернизировать и минимальную стоимость, за которую можно модернизировать такое число каналов.

Ограничения

2 ≤ n ≤ 10⁵, 1 ≤ k ≤ 100

1 ≤ p_i ≤ i, 0 ≤ w_i ≤ 10⁹

Система оценки

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

Пояснение к примеру

Конфигурация сети в первом примере до и после модернизации показана на рисунке ниже. Каналы, которые необходимо модернизировать, показаны жирными линиями. Максимальное число каналов, которое можно модернизировать, равно 4. Стоимость модернизации любого канала равна 0 и не показана.

Есть и другие подходящие решения, в которых модернизируется 4 канала.

Конфигурация сети во втором примере до и после модернизациии показана на рисунке ниже. Каналы, которые необходимо модернизировать, показаны жирными линиями. Максимальное число каналов, которое можно модернизировать, равно 6. Стоимость модернизации канала показана рядом с каналом, суммарная стоимость модернизации каналов в оптимальном решении равна 27.

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

8 2
1 0
1 0
1 0
2 0
2 0
2 0
1 0

4 0

8 3
1 5
1 2
1 4
2 6
2 7
2 2
1 6

6 27

Задача 4. Подарки ≡

Условие

Дед Мороз предлагает Вове выбрать подарки на Новый год.

Перед мальчиком лежат n подарков в ряд. Каждый подарок характеризуется целым числом, у i-го подарка оно равно a_i — количество удовольствия, которое подарок принесёт Вове. Удовольствие может быть как положительным, так и отрицательным, а также равным нулю.

Дед Мороз предложил Вове выбрать два числа l и r таких, что 1 ≤ l ≤ r ≤ n, и взять все подарки с номерами от l до r. Однако k подарков с максимальными характеристиками среди выбранных Вова должен отдать своей младшей сестре Маше. Остальные подарки Вова забирает себе.

Вова хочет выбрать числа l и r так, чтобы суммарное удовольствие от подарков, доставшихся именно ему, было максимальным. Общее удовольствие от набора подарков — это сумма значений a_i для подарков в наборе.

Помогите Вове выбрать числа l и r так, что 1 ≤ l ≤ r ≤ n, r − l + 1 ≥ k и общее удовольствие от выбранных подарков без учёта подарков, доставшихся Маше, максимально.

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

В первой строке записаны два целых числа n и k (1 ≤ n ≤ 200 000, 0 ≤ k ≤ min(100, n)) — количество подарков перед Вовой и количество подарков, которые требуется отдать Маше.

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

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

Выведите единственное число — общее удовольствие от выбранных Вовой подарков без учёта тех, что достались Маше.

Ограничения

1 ≤ n ≤ 200 000, 0 ≤ k ≤ min(100, n)

 − 10⁹ ≤ a_i ≤ 10⁹

Система оценки

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

Замечание

В первом примере Вова ничего не должен отдавать Маше, поэтому он выберет l = 3, r = 5, и общее удовольствие от выбранных подарков будет равняться 5 + ( − 1) + 7 = 11.

Во втором примере Вова должен будет отдать Маше подарок с самым большим количеством удовольствия. Тогда он так же выберет l = 3, r = 5, однако общее удовольствие будет равняться 5 + ( − 1) = 4.

В третьем примере Вова должен отдать два подарка с наибольшими характеристиками. В таком случае одним из оптимальных вариантов будет выбрать l = 1, r = 2.

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

5 0
2 -4 5 -1 7

11

5 1
2 -4 5 -1 7

4

5 2
2 -4 5 -1 7

0