Всем привет! А вот и разбор контеста!
Задача А — Ромка и калькулятор
Хочу сделать несколько замечаний по задаче. Вообще здесь не должны заходить long long, но я забыл в генераторе после проверки поставить обратно $$$10^18$$$. Второе замечание такое: заметил, что у многих полетели задачи из-за того, что они просто выводили trunk(ans). Но требовалось вывести целое число, а trunk возвращает double, поэтому большие числа выводились у многих в экспоненциальной форме, что неверно. Обработка первого, второго и третьего запросов должна быть ясна, запрос четвёртого типа я пояснил. Многие писали, что не описано деление на 0. Но в условии гарантируется существование ответа Для запроса 5-го типа я забыл написать, что a >= 0 && b > 0. А так задача довольно простая, если писать её на Python или с помощью int128 на С++.
Задача B — Ромка и рассыпавшиеся числа
Задача довольно простая, если подумать логически. Первое условие, которое должно выполняться — s >= кол-во нечётных, т.к минимальное нечётное — 1, а их минимальная сумма должна быть меньше либо равна сумме по всему массиву. Второе, что можно заметить — s % 2 должно быть равно остатку от деления кол-ва нечётных на 2, т.к только нечётные влияют на чётность итогового выражения(математика). Теперь просто проверим, выполняются ли оба условия и всё
Задача C — Ромка и пропуски на выпускной
Многим показалась эта задача простой. Я соглашусь, необходимое наблюдение только в том, что мы отвечаем на запросы в режиме реального времени. Поэтому для запроса 1-го типа мы ставим имя в set. Для запроса 2-го типа мы проверяем, есть ли имя в set. Всё
Задача D — Ромка и парадокс групп
Стандартная задача. Для запроса на сумму можно использовать дерево отрезков или префиксные суммы. Для запроса на максимум построим ДО на максимум. Теперь осталось вывести sum(l, r) — max(l, r)
Задача E — Ромка и отдых на каникулах
Я придумал эту задачу уже давно. Она была рассчитана на то, что вы заметите треугольник Паскаля. Это самое главное, что требовалось. Теперь остаётся лишь найти его ярус: n = i + j — 2 и номер: k = j — 1. Теперь найдём ответ по формуле n! / k! / (n — k)! по модулю $$$10^9$$$ + 7. Факториал берём по модулю динамически.
Задача F — Ромка и сложный эксперимент
Здесь всё довольно просто. Необходимо лишь использовать формулу для мат. ожидания. Её можно загуглить. Условие было немного непонятным, так что я его проясню: человек с вероятностью $$$a[i]$$$ идёт прямо, а с вероятностью $$$100-a[i]$$$ продолжит идти прямо (до следующего поворота)
