Задача A. Any number

Автор:A. Verkholat   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

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

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

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

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

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

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

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

Ограничения

0 ≤ A ≤ 500

0 ≤ B ≤ 500

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

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

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

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

Стандартный вход Стандартный выход
1
312 353
YES
2
102 357
NO

Задача B. Bearded joke

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

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

Письмо на Балабановскую спичечную фабрику. "Я постоянно считаю спички у вас в коробках — их то 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 спичками.

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

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

Стандартный вход Стандартный выход
1
4
3

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

Автор:Г. Гренкин, И. Блинов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

AUC вычисляется следующим образом. Вычисляется число реальных единиц K1 и число реальных нулей K0, расположенных в положительной полуплоскости. Тогда AUC = 0.5 + 0.5 ⋅ K1N1 − 0.5 ⋅ K0N0, где N1 – общее число единиц, N0 – общее число нулей.

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

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

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

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

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

Ограничения

2 ≤ n ≤ 1000 0 ≤ pi, bi ≤ 109 ci ∈ 0, 1

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

Стандартный вход Стандартный выход
1
4
0.0 0.0 1
1.0 1.0 1
0.0 1.0 0
1.0 0.0 0
0.75
2
5
1 1 1
0 1 1
1 0 1
0 0 1
3 2 0
1

Задача D. Discarding numbers

Автор:A. Verkholat   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 109

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, которое является ответом.

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

Стандартный вход Стандартный выход
1
10 5
3

Задача E. Explorer kit

Автор:И. Блинов   Ограничение времени:2 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

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

Первая строка содержит одно целое число n. Далее следует n троек чисел ti1, ti2, ti3. Следующая строка содержит одно целое число h. Далее следует h четвёрок целых чисел tj1, tj2, tj3 и pj. Гарантируется, что решение всегда существует.

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

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

Ограничения

1 ≤ n, h ≤ 100000 1 ≤ ti1, ti2, ti3, tj1, tj2, tj3 ≤ 109 0 ≤ pj ≤ 100

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

Стандартный вход Стандартный выход
1
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
2
1
1 1 1
1
1 2 2 50
5.99

Задача F. Fast Breeding

Автор:И. Блинов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  

Условие

Рисориус занимается селекцией цветов. Всего в её коллекции n видов растений их неограниченное количество. Каждое растение характеризуется окрасом цветка. Цвет i-го растения шифруется 3-мя числами в диапазоне от 1 до 64 (ri, gi, bi). При скрещивании двух видов растений с окрасами (ra, ga, ba) и (rb, gb, bb) окрас нового цветка вычисляется следующий образом: (ra + rb2, ga + gb2, ba + bb2). Кроме того при скрещивании одно растение всегда должно быть из первый n видов растений иначе результат скрещивания будет нежизнеспособным.

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

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

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

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

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

Ограничения

1 ≤ n ≤ 100

1 ≤ r, g, b, ri, gi, bi ≤ 64

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

Стандартный вход Стандартный выход
1
32 32 32
2
1 1 1
64 64 64 
1
2
64 64 64
2
1 1 1
63 63 63 
-1

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

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

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

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

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

Ограничения

2 ≤ a < n ≤ 109

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

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

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

Стандартный вход Стандартный выход
1
3
10
30
42
28

Задача H. Hidden tree

Автор:A. Usmanov   Ограничение времени:1 сек
Ввод / вывод:интерактивный   Ограничение памяти:256 Мб

Условие

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Язык C++ Pascal Java Python
Код cout.flush() flush(output) System.out.flush() stdout.flush()

Ограничения

3 ≤ N ≤ 1000

1 ≤ Ai, Bi ≤ N

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

Стандартный вход Стандартный выход
1
6

ok
+ 5 6

ok
+ 1 6

ok

+ 1 2


+ 1 3


+ 2 4
2
3

ok
+ 2 3

+ 1 2

Задача I. Item enhancement

Автор:A. Verkholat   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 105

1 ≤ K ≤ 109

1 ≤ M ≤ 109

1 ≤ Ai ≤ 109

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

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
3 1 1
1 1 1
3
2
4 1 1
5 2 4 3
4
3
5 2 2
1 1 1 1 2
2
4
2 1 100
1 1
1
5
2 2 100
1 3
1

Задача J. Just pizza

Автор:И. Блинов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 100000 1 ≤ ci ≤ 109

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

Стандартный вход Стандартный выход
1
3
360
720
720
YES
2
4
90
45
45
180
YES
3
5
180
180
180
180
180
NO
4
3
1080
180
180
NO

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

Автор:twitch.tv/jollyfuzz   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 100

1 ≤ |Xi| ≤ 100

1 ≤ Mi ≤ 1000

1 ≤ Ti,j ≤ 107

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

Стандартный вход Стандартный выход
1
3
build_stage
3
5 7 1
test_stage
5
1 6 8 9 2
deploy_stage
2
2 2
18

Задача L. Long sleep

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

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

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

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

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

Ограничения

1 ≤ c ≤ n ≤ 105

1 ≤ wi ≤ 109

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

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

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

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
5
3
1 2 3 4 5
7

Задача M. Match Schedule

Автор:И. Блинов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 100

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

Стандартный вход Стандартный выход
1
5
XAAHH
HXAAH
HHXAA
AHHXA
AAHHX
2
2
XA
HX

0.684s 0.012s 43