Задача 1. Стремление к нулю ≡

Условие

Дано число N и массив из S целых чисел A_i.

За одну операцию можно заменять число N на любое из чисел N + A_i, N − A_i, N × A_i, N / A_i.

Второй операнд может быть любым элементом массива A.

Деление выполняется нацело, с округлением вниз.

Необходимо рассчитать минимальное количество операций, необходимых, чтобы получить из числа N число 0.

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

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

Вторая — целое число S.

Третья — S целых чисел, массив A.

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

Выходные данные должны содержать одно целое число — минимальное количество операций.

Ограничения

0 ≤ N, A_i ≤ 2*10⁹

1 ≤ S ≤ 100

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

100 / 25 = 4 ; 4 - 4 = 0

100 / 11 = 9 ; 9 / 11 = 0

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

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

100
6
4 7 10 5 25 11

2

Задача 2. Фильтр товаров ≡

Условие

Варфоломей устроился программистом-стажёром в одну известную компанию. Вместе со своим наставником Иннокентием они разрабатывали приложение для подбора товаров по пожеланиям клиентов. За продуктивную рабочую неделю они реализовали методы выбора товаров нужной категории, и тут Иннокентий заболел и вышел на больничный, но на носу дедлайн! Варфоломей обращается к дружному коллективу олимпиадников за помощью: помогите ему закончить приложение!

Для реализации главной задачи, а именно выбора узкой категории товаров, Варфоломей предоставил вам следующие данные: N - количество подобранных товаров соответствующей категории, для каждого из которых присутствуют 3 характеристики, а именно: цвет (R, G, B), размер (S, M, L) и цена (целое число).

К дедлайну необходимо сделать возможным обработку K запросов от клиентов следующего вида: 1 символ означает цвет, 2 — означает размер, а 3 символ, равный A либо D, означает в последовательности возрастания или убывания необходимо вывести список найденных товаров. Во время составления запросов клиенту может быть неважен цвет товара, его размер или последовательность вывода, тогда вместо символа нужной категории он ставит символ "_". Если клиенту не важна последовательность вывода или товары имеют одинаковую стоимость, то необходимо сохранить исходный порядок Варфоломей и его наставник надеются на вашу помощь!

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

Первая строка входных данных содержит целое число N. Далее идут N строк, содержащих 3 характеристики товара (цвет, размер и цену). Строка номер N+1 содержит целое число K, далее идут K строк клиентских запросов.

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

Выходные данные должны содержать K строк с перечислением товаров, удовлетворяющих запросу. Если для запроса не найдется хотя бы один товар, нужно вывести −1. Если клиенту не важна последовательность вывода или товары имеют одинаковую стоимость, то необходимо сохранить исходный порядок.

Ограничения

0 ≤ N, K ≤ 10²

Описание подзадач и системы оценивания

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

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

4
R S 5
G L 8
G S 7
B M 9
5
R _ A
B L D
G _ _
G L _
G _ A

R S 5
-1
G L 8 G S 7
G L 8
G S 7 G L 8

Задача 3. Типичная вечеринка с бассейнами ≡

Условие

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

Для бассейной вечеринки нужно, чтобы все бассейны с водой были расположены рядом друг с другом (между каждыми двумя наполненными бассейнами не должно быть бассейнов без воды). Чтобы достичь этого, друзья могут перелить воду из любого наполненного бассейна в любой из двух соседних, если соседний не наполнен. Какое минимальное количество переливаний воды из бассейна в бассейн Кириллу и друзьям понадобится сделать, чтобы все было готово к вечеринке?

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

Первая строка входных данных содержит целые числа N К, где N — общее количество бассейнов, K — количество бассейнов, наполненных водой.

Вторая строка входных данных содержит строку S, состоящую из N символов 0 и 1. S_i = 1, если бассейн на позиции i наполнен, S_i = 0 в противном случае.

Гарантируется, что S содержит ровно K единиц.

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

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

Ограничения

1 ≤ K ≤ N ≤ 1000000

Описание подзадач и системы оценивания

Решение оценивается пропорционально количеству успешно пройденных тестов.

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

10 3
0010001010
    

4
    

10 2
0000011000
    

0
    

Задача 4. Подстрока с уникальными символами по краям ≡

Условие

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

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

Входные данные содержат одну строку s.

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

В ответ нужно вывести целое число — длину подходящей подстроки.

Ограничения

2 ≤ |s| ≤ 10⁶

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

В первом примере ответом могут быть подстроки abc и bcb. Во втором — bacab.

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

aabcb

3

abacaba

5

Задача 5. Танковый симулятор ≡

Условие

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

Формат входного файла

Первая строка входных данных содержит 3 целых числа x_c, y_c, r_c — координаты и радиус мины. Вторая строка содержит одно целое число N — количество вершин в многоугольнике, описывающем танк. Следующие N строк содержат N пар целых чисел (x_i, y_i) (по одной паре в строке) — координаты вершин выпуклого многоугольника, описывающего танк, в порядке обхода по часовой стрелке.

Формат выходного файла

Выходные должны содержать одно вещественное число — площадь пересечения мины и танка с точностью не менее двух знаков после запятой.

Ограничения

−1000 ≤ x_c, y_c, r_c, x_i, y_i ≤ 1000

3 ≤ N ≤ 10³

Описание подзадач и системы оценивания

Решения, работающие для −10 ≤ x_c, y_c, r_c, x_i, y_i ≤ 10, оцениваются из 50 баллов. Баллы выставляются за каждый успешно пройденный тест.

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

1 1 1
4
0 0 0 1 1 1 1 0

0.785398163

0 0 1
3
0 0
0 1
1 0

0.5

0 0 4
4
0 0
0 2
4 4
2 0

7.07035