Задача A. Any number ≡

Условие

У Васи есть три целых числа: A, B и C, изначально число C равно нулю.

Он может использовать две следующие операции любое количество раз.

1) Прибавить число A к числу C.

2) Вычесть число B из числа C.

Вася загадал некоторое целое число X (возможно отрицательное) и хочет получить его из числа C.

Определите, всегда ли это возможно?

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

Первая строка содержит два целых числа: A и B.

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

Ответ на задачу - YES или NO.

Ограничения

0 ≤ A ≤ 500

0 ≤ B ≤ 500

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

В первом примере можно доказать что Вася сможет получить любое целое число.

Во втором примере Вася не сможет получить число 14.

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

312 353

YES

102 357

NO

Задача B. Bearded joke ≡

Условие

Бородатый анекдот:

Письмо на Балабановскую спичечную фабрику. "Я постоянно считаю спички у вас в коробках — их то 59, то 60, а иногда и 58. Вы там сумасшедшие что ли все???"

Пенсионер Одержимов произвёл очередную контрольную закупку k ≥ 2 коробков спичек. Его опасения подтвердились — во всех коробках оказалось различное количество спичек и опять они оказались последовательными натуральными числами. Старик полюбовался на сложенный из всех спичек красивый равносторонний треугольник со стороной n, разбитый на единичные треугольники, и принялся за очередное письмо.

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

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

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

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

Ограничения

1 ≤ n ≤ 500000

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

В примере дано n = 4 (смотри рисунок). В получившейся фигуре ровно 30 спичек.

Пенсионер мог купить три коробка, в которых оказалось 9, 10 и 11 спичек.

Мог купить четыре коробка с 6, 7, 8 и 9 спичками.

А мог купить пять коробков с 4, 5, 6, 7 и 8 спичками.

Других подходящих решений нет.

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

4

3

Задача C. Cutpoint on the plane ≡

Условие

В городской поликлинике поставили задачу выяснить, какие сочетания пульса p_i и артериального давления b_i приводят к плохому самочувствию. С этой целью врачи измерили эти параметры у n пациентов, спросив у них о самочувствии. Получилась выборка с двумя признаками, разделенная на два класса c_i: «1» - плохое самочувствие, «0» - нормальное самочувствие.

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

Требуется провести прямую через две точки из выборки так, чтобы при предсказании «1» по одну сторону от прямой или на самой прямой и «0» в остальных случаях классификация получилась наилучшей.

AUC вычисляется следующим образом. Вычисляется число реальных единиц K₁ и число реальных нулей K₀, расположенных в положительной полуплоскости. Тогда AUC = 0.5 + 0.5 ⋅ K₁N₁ − 0.5 ⋅ K₀N₀, где N₁ – общее число единиц, N₀ – общее число нулей.

Отметим, что положительной (соответствующей классу «1») считаем ту полуплоскость, в которой AUC больше.

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

Первая строка содержит одно целое число n. Далее следует n троек чисел p_i, b_i, c_i. Числа p_i, b_i вещественные, c_i — это 0 или 1. Гарантируется, что существует хотя бы одна точка относящаяся к классу 1 и хотя бы одна точка относящаяся к классу 0. Никакие три точки (p_i, b_i) не лежат на одной прямой.

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

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

Ограничения

2 ≤ n ≤ 1000 0 ≤ p_i, b_i ≤ 10⁹ c_i ∈ 0, 1

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

4
0.0 0.0 1
1.0 1.0 1
0.0 1.0 0
1.0 0.0 0

0.75

5
1 1 1
0 1 1
1 0 1
0 0 1
3 2 0

1

Задача D. Discarding numbers ≡

Условие

Вася выписал в ряд все числа от 1 до N включительно.

Пока не кончатся числа, он использует следующий алгоритм.

1) Отбрасывает число из начала списка.

2) Отбрасывает число из конца списка.

3) Переписывает числа в обратном порядке.

4) Возвращается к пункту 1.

Какое число Вася отбросит K-ым по счету?

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

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

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

Одно число, которое Вася отбросит K-ым по счету.

Ограничения

1 ≤ N ≤ 10⁹

1 ≤ K ≤ N

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

Изначальный список: 1 2 3 4 5 6 7 8 9 10.

Вася отбросил число из начала: 2 3 4 5 6 7 8 9 10.

Отбросил из конца: 2 3 4 5 6 7 8 9.

Развернул список: 9 8 7 6 5 4 3 2.

Отбросил из начала: 8 7 6 5 4 3 2.

Отбросил из конца: 8 7 6 5 4 3.

Развернул список: 3 4 5 6 7 8.

Отбросил из начала число 3, которое является ответом.

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

10 5

3

Задача E. Explorer kit ≡

Условие

Рисориус играет в свою любимую игру Дока 2, внутри игры добавили событие Павшая корона. Событие представимо в виде цепочки из n последовательных переходов, находясь на чекпоинте i можно перейти только на чекпоинт i + 1. Для прохода от чекпоинта i на чекпоинт i + 1 надо собрать три жетона t_i1, t_i2, t_i3. После перехода от одного чекпоинта к другому все накопленные жетоны сгорают.

В игре всего h героев, за победу на j-м герое дают жетоны t_j1, t_j2, t_j3. Вероятность того, что Рисориус победит на k-м герое p_k. Кроме того если игрок проигрывает на одном герое 10 раз подряд, находясь на одном чекпоинте, он всё равно получает все три жетона.

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

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

Первая строка содержит одно целое число n. Далее следует n троек чисел t_i1, t_i2, t_i3. Следующая строка содержит одно целое число h. Далее следует h четвёрок целых чисел t_j1, t_j2, t_j3 и p_j. Гарантируется, что решение всегда существует.

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

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

Ограничения

1 ≤ n, h ≤ 100000 1 ≤ t_i1, t_i2, t_i3, t_j1, t_j2, t_j3 ≤ 10⁹ 0 ≤ p_j ≤ 100

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

3
1 2 3
1 1 1
3 4 5
5
1 2 2 50
1 3 4 25
5 1 1 25
5 5 5 100
6 7 8 100

16.32

1
1 1 1
1
1 2 2 50

5.99

Задача F. Fast Breeding ≡

Условие

Рисориус занимается селекцией цветов. Всего в её коллекции n видов растений их неограниченное количество. Каждое растение характеризуется окрасом цветка. Цвет i-го растения шифруется 3-мя числами в диапазоне от 1 до 64 (r_i, g_i, b_i). При скрещивании двух видов растений с окрасами (r_a, g_a, b_a) и (r_b, g_b, b_b) окрас нового цветка вычисляется следующий образом: (⌊r_a + r_b2⌋, ⌊g_a + g_b2⌋, ⌊b_a + b_b2⌋). Кроме того при скрещивании одно растение всегда должно быть из первый n видов растений иначе результат скрещивания будет нежизнеспособным.

К Рисориус поступил заказ на растение с окрасом (r, g, b). Какое минимальное количество скрещиваний нужно провести для получения искомого растения?

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

Первая строка содержит три целых числа (r, g, b). Вторая строка входных данных содержит одно целое число n. Далее следует n строк содержащих по три целых числа r_i, g_i, b_i.

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

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

Ограничения

1 ≤ n ≤ 100

1 ≤ r, g, b, r_i, g_i, b_i ≤ 64

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

32 32 32
2
1 1 1
64 64 64 

1

64 64 64
2
1 1 1
63 63 63 

-1

Задача G. Gray, black and white squares ≡

Условие

У Тимофея есть две полупрозрачные пленки в серо-белую клетку размером n × n. На первой из них размер клетки 1 × 1, на второй — a × a, левый верхний угол у обоих клеток серый. Сегодня мальчик положил две пленки друг на друга. В результате, там, где серые квадратики наложились на серые, получился черный цвет, там, где серые квадратики наложились на белые, остался серый цвет, там, где белые квадратики наложились на белые, остался белый цвет.

Определите, сколько всего единичных квадратиков черного, серого и белого цвета получилось.

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

Две строки входных данных содержат два натуральных числа a и n.

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

Выведите три натуральных числа — количество черных, серых и белых единичных квадратиков.

Ограничения

2 ≤ a < n ≤ 10⁹

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

Смотри рисунок.

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

3
10

30
42
28

Задача H. Hidden tree ≡

Условие

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

У мальчика Пети есть N вершин. Он хочет соединить их ребрами, чтобы получилось дерево. Напомним, что дерево — это связный граф из N вершин и N − 1 ребра.

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

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

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

В первой строке входных данных записано целое число N — количество вершин в дереве.

Протокол взаимодействия

Чтобы добавить ребро, ваша программа должна вывести "+ Ai Bi", где A_i, B_i — целые числа, номера вершин, которые нужно соединить ребром.

На это программа жюри ответит вашей программе строчкой "ok". Если после этого еще можно добавлять ребра, то программа жюри также выведет "+ Ai Bi", где A_i, B_i — целые числа, номера вершин, которые соединяются ребром. Гарантируется, что программа жюри добавляет ребра согласно всем описанным правилам. После этого ход вновь переходит вашей программе.

Когда в дереве будет ровно N − 1 ребро, ваша программа должна завершиться.

Если ваша программа добавит лишнее ребро, то она получит вердикт "Wrong answer".

Если ваша программа сделает недопустимый запрос, то она получит вердикт "Presentation error".

Если ваша программа получила от программы жюри строку "error" вместо "ok", то она должна немедленно завершиться. Такое возможно, если ваша программа нарушила протокол взаимодействия. Если ваша программа не завершится, то вердикт может отличаться от описанных выше (например, может быть вердикт "Runtime error").

Каждый запрос должен быть одиночной строкой заканчивающейся одиночным переводом строки (\n). Буфер вывода необходимо сбрасывать после каждой строки:

Ограничения

3 ≤ N ≤ 1000

1 ≤ A_i, B_i ≤ N

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

6

ok
+ 5 6

ok
+ 1 6

ok

+ 1 2


+ 1 3


+ 2 4

3

ok
+ 2 3

+ 1 2

Задача I. Item enhancement ≡

Условие

Петя очень любит играть в MMORPG и хочет побеждать всех в PvP.

Он только что купил крутое оружие и пошел его точить.

Изначально уровень заточки равен нулю.

У Пети в инвентаре имеется N камней заточки разных уровней.

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

Также имеется возможность создать из M камней одного уровня камень уровнем на 1 больше.

Насколько максимально Петя сможет заточить свое оружие?

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

Первая строка содержит три целых числа: N, K и M

N - количество камней заточки.

K - количество камней для поднятия заточки на 1 уровень.

M - количество камней для крафта камня уровнем выше.

Вторая строка содержит массив A из N целых чисел - уровни камней заточки имеющихся у Пети.

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

Одно целое число - максимальный уровень заточки оружия, которого можно достичь.

Ограничения

1 ≤ N ≤ 10⁵

1 ≤ K ≤ 10⁹

1 ≤ M ≤ 10⁹

1 ≤ A_i ≤ 10⁹

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

В первом примере Петя создает 3 камня 3-го уровня и использует их по очереди.

Во втором примере Петя использует камни в порядке 2, 3, 4, 5.

В третьем примере использует 2 камня 1-го уровня, из оставшихся двух создает камень второго уровня и использует 2 камня 2-го уровня.

В четвертом примере использует 1 камень 1-го уровня и на этом останавливается.

В пятом примере используются один раз оба камня.

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

3 1 1
1 1 1

3

4 1 1
5 2 4 3

4

5 2 2
1 1 1 1 2

2

2 1 100
1 1

1

2 2 100
1 3

1

Задача J. Just pizza ≡

Условие

Слон Пахом готовит пиццу, у него есть ровно одна основа которая выглядит как окружность. Для начинки имеется n ингредиентов, каждый ингредиент характеризуется числом c_i тем какой сектор пиццы может быть покрыт этим ингредиентом (360 означает, что его хватит ровно на один слой). Для того, чтобы пицца была вкусной, должны быть выполнены следующие условия:

• В каждой точке пиццы должно быть одинаковое количество слоёв начинки
• При это два слоя одинаковой начинки идущие подряд недопустимы
• Вся начинка должна быть использована
• Внутри слоя начинка может быть разных видов

Сможет ли Пахом приготовить вкусную пиццу?

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

Первая строка содержит одно целое число n. В следующих n строках содержатся числа c_i.

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

Выведите YES если вкусную пиццу возможно приготовить, в противном случае выведите NO.

Ограничения

1 ≤ n ≤ 100000 1 ≤ c_i ≤ 10⁹

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

3
360
720
720

YES

4
90
45
45
180

YES

5
180
180
180
180
180

NO

3
1080
180
180

NO

Задача K. Kolya writes a feature ≡

Условие

Команда Коли перешла на новый инструмент автоматизации процессов непрерывной интеграции (CI) и непрерывной доставки (CD) - GitClub CI/CD.

Пайплайн состоит из N стадий (stages), а стадии в свою очередь из M_i заданий (jobs).

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

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

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

Первая строка содержит число N - количество стадий.

Далее следуют описания N стадий, описание каждой стадии состоит из трех строк:

Первая строка - строка из маленьких латинских букв и знаков подчеркивания X_i - имя стадии.

Вторая строка - целое число M_i - количество заданий в стадии.

Третья строка - массив целых чисел T_i - длительности каждого задания в секундах.

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

Одно целое число — общее время выполнения пайплайна в секундах.

Ограничения

1 ≤ N ≤ 100

1 ≤ |X_i| ≤ 100

1 ≤ M_i ≤ 1000

1 ≤ T_i,j ≤ 10⁷

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

3
build_stage
3
5 7 1
test_stage
5
1 6 8 9 2
deploy_stage
2
2 2

18

Задача L. Long sleep ≡

Условие

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

На то, чтобы уронить предмет весом w_i одному коту требуется w_i минут, после чего он переходит к следующему незанятому предмету (в том порядке, в котором они стоят). Коты не помогают друг другу (если один освободился раньше, то будет просто наблюдать, как другие роняют последние предметы). Завершив перемещение всех предметов, коты побегут будить хозяйку отчётом о проделанной работе.

Определите, сколько времени осталось спать Наташе.

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

Две строки входных данных содержат натуральные числа n и c. В третьей строке через пробел расположены n натуральных чисел w_i — веса и порядок предметов на столе.

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

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

Ограничения

1 ≤ c ≤ n ≤ 10⁵

1 ≤ w_i ≤ 10⁹

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

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

0 минут: коты приступают к работе: первый кот будет ронять первый предмет весом 1, второй — второй (весом 2), третий — третий (весом 3).

1 минута: первый кот уронил предмет весом 1 и уходит ронять предмет весом 4.

2 минуты: второй кот уронил предмет весом 2 и уходит ронять предмет весом 5.

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

5 минут: первый кот уронил предмет весом 4 и переходит в режим наблюдения за своими товарищами.

7 минут: второй кот уронил предмет весом 5. Все предметы упали, коты уходят будить Наташу.

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

5
3
1 2 3 4 5

7

Задача M. Match Schedule ≡

Условие

В футбольном турнире участвует n команд. Каждая команда играет с каждой ровно один раз. Требуется распределить матчи так, чтоб для каждой команды количество домашних матчей отличалось от количества гостевых матчей не более чем на 1.

Нужно вывести расписание в виде таблицы n на n. Где i-я строка описывает матчи i-й команды.

• Eсли j-й элемент в ней равен 'H' значит матч между и i и j командой пройдёт на домашнем стадионе i-й команды.
• Если же он равен 'A', то матч пройдёт на домашнем стадионе j-й команды.
• Диагональный элемент (где i = j) должен быть отмечен символом 'X' так как команды не может играть сама против себя.

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

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

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

Выведите n строк по n символов 'H', 'A' или 'X' описывающих искомое расписание игр. В расписании матчей не должно быть противоречий.

Ограничения

1 ≤ n ≤ 100

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

5

XAAHH
HXAAH
HHXAA
AHHXA
AAHHX

2

XA
HX