Задача 1. Поиск трапеции ≡

Условие

Ваня купил себе VR-гарнитуру и решил поиграть. Для начала ему необходимо разметить VR-зону в комнате. Для этого Ваня хочет использовать изоленту. У него уже есть N отрезанных кусков длиной a_i. VR-зона должна иметь форму прямоугольной трапеции. Каждая сторона трапеции должна быть образована ровно одним куском изоленты.

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

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

Первая строка содержит единственное число N. Следующие N строк содержат целые числа — длины отрезков a_i

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

Выведите 4 индекса отрезков в порядке возрастания или  − 1, если невозможно получить прямоугольную трапецию. Индексация начинается с нуля.

Если существует несколько ответов, выведите трапецию с максимальной площадью, а среди таких — с минимальным первым индексом.

Ограничения

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

5
12
10
3
7
23

-1

6
14
12
16
21
15
25

1 2 4 5

Задача 2. Разделение прямоугольника ≡

Условие

Аня играет в новую настольную игру «Клетчатое королевство».

Рассмотрим прямоугольное клетчатое поле размером a × b.

Необходимо разделить его на m прямоугольников вертикальными или горизонтальными разрезами. Прямоугольники не обязательно должны получиться равными. Необходимо суммарно провести ровно k разрезов.

Каждый разрез представляет собой прямую линию от одного края поля до другого края поля. Разрезы разрешено делать только по границам клеток — линиям сетки.

Выведите, сколько провести горизонтальных (0 ≤ h < a) и сколько вертикальных (0 ≤ v < b) разрезов. Если поле можно разрезать несколькими способами, выведите тот, в котором горизонтальных разрезов меньше. Если поле нельзя разрезать требуемым образом, выведите  − 1.

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

В первой строке дано ровно одно целое число t — количество тестов.

В следующих t строках находится описание тестов: в i-й строке через пробел даны четыре целых числа: a, b, k, m — высота и ширина поля, количество разрезов и количество прямоугольников соответственно.

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

Для каждого теста выведите через пробел ровно два целых числа h и v — количество горизонтальных и количество вертикальных разрезов, если прямоугольное клетчатое поле можно разрезать требуемым образом, в противном случае выведите число  − 1.

Ограничения

1 ≤ t ≤ 100

1 ≤ a, b ≤ 10⁹, 0 ≤ k ≤ 2 ⋅ 10⁹, 1 ≤ m ≤ 10¹⁸, k < m

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

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

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

В приведенном примере содержится три теста:

1. В первом тесте поле можно разрезать, как показано на рисунке:

   

2. Во втором тесте поле нельзя разрезать требуемым образом.
3. В третьем тесте поле можно разрезать, как показано на рисунке:

   

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

3
2 2 1 2
1 2 2 3
3 5 5 12

0 1
-1
2 3

Задача 3. Метрострой ≡

Условие

Буровая установка «Мегабур 2022» для прокладки туннелей метро Байтсбурга имеет n двигателей. Питание установки устроено таким образом, что на все двигатели подается одно и то же целочисленное напряжение x.

У каждого двигателя есть два режима, если на него подается напряжение x, то i-й двигатель работает в первом режиме, если x ≤ z_i и во втором режиме, если x > z_i.

При этом i-й двигатель характеризуется удельной мощностью a_i в первом режиме и b_i во втором режиме. Это означает, что увеличение напряжения на 1 когда двигатель находится в первом режиме, приводит к увеличению его мощности на a_i, а во втором режиме приводит к увеличению его мощности на b_i. Иначе говоря, при подаче напряжения x, если i-й двигатель находится в первом режиме он работает с мощностью a_i x, а если во втором режиме, то с мощностью a_i z_i + b_i(x − z_i).

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

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

Первая строка ввода содержит целые числа n и p.

Следующие n строк описывают двигатели и содержат по три целых числа z_i, a_i, b_i.

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

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

Ограничения

1 ≤ n ≤ 100, 1 ≤ p ≤ 10¹²

1 ≤ z_i ≤ 10⁹, 1 ≤ a_i, b_i ≤ 10⁴

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

1 6
4 1 2

5

3 15
2 3 3
4 2 1
5 2 2

3

Задача 4. Фантастическое чёрно-красное дерево ≡

Условие

Существует фантастическое черное-красное дерево - граф, который представляет из себя дерево (связный граф без циклов), в котором каждая вершина покрашена в один из двух цветов - красный или черный.

У вас есть не менее замечательная строка s, состоящая из K символов ‘r' и 'b’. Ваша задача - выяснить сколько существует путей по дереву, таких, что если выписать цвета вершин, по которым вы прошлись, то получится строка s.

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

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

В первой строке целое число N- количество вершин в графе.

Далее строка g состоящая из N символов ‘r' и 'b’, описывающая цвета вершин дерева.

Далее строка s, состоящая из K символов ‘r' и 'b’.

В следующих строках два целых числа - a_i и b_i - начало и конец ребра.

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

Ограничения

2 ≤ K ≤ N ≤ 10⁴

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

5
brbrr
rbr
1 3
4 3
3 5
2 3

6

5
brrbr
rb
1 2
1 5
3 4
5 4

4

Задача 5. Дробные монеты ≡

Условие

В одном государстве в обращении находятся монеты достоинством xy бурлей, где 1 ≤ x < y и xy — несократимая дробь. Например, при y = 5 в ходу монеты достоинством 15, 25, 35 и 45 бурлей, а при y = 6 — монеты 16 и 56.

Хорошим тоном для банковских работников страны является набор требуемой суммы наименьшим количеством монет. Например, если клиент хочет снять сумму 136, ему выдадут пять монет: две монеты достоинством 56 и три монеты достоинством 16.

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

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

Первая строка входного файла содержит натуральное число p — числитель требуемой для выдачи суммы, вторая строка содержит натуральное число y — знаменатель достоинств всех монет в стране.

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

Выведите одно натуральное число — ответ на вопрос задачи.

Ограничения

1 ≤ p ≤ 10⁵

2 ≤ y ≤ 100

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при y = 2, получат не менее 10 баллов.

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

В первом примере дано y = 15. В обращении находятся монеты достоинством 115, 215, 415, 715, 815, 1115, 1315 и 1415.

Для набора суммы 1715 достаточно взять две монеты, например 1315 и 415.

Во втором примере дано y = 2. В обращении находятся только монеты достоинством 12.

Для набора суммы 42 = 21 необходимо взять четыре монеты.

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

17
15

2

4
2

4