Муниципальный этап по информатике в ХМАО-Югре, 9-11 классы

Дробь может быть представлена в виде конечной десятичной дроби, если её знаменатель не имеет простых делителей, отличных от 2 и 5, т. е. может быть записан как $$$2^a5^b$$$. Если это невозможно, то выводим NO. При переводе в десятичную дробь знаменатель должен иметь вид $$$10^k$$$, для этого нужно умножать числитель и знаменатель на 2 или 5, пока степени 2 и 5 в знаменатели не станут равны. Степень $$$k$$$ является ответом на задачу, и она может быть найдена как максимум из степеней $$$a$$$ и $$$b$$$.

Посчитаем сумму всех чисел. Затем постепенно переносим элементы последовательности из второй части в первую и проверяем, не увеличился ли результат.

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

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

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

Сначала нужно написать функцию, моделирующую поедание ряда сосисок. При этом каждый участник забирает сосиски, которые он может съесть за время $$$t$$$. Если не вcе сосиски будут съедены, функция возвращает false, иначе true. С помощью бинарного поиска находим наименьшее $$$t$$$, при котором все сосиски будут съедены.

Частичное решение можно получить, постепенно проверяя все варианты $$$t$$$ от 1.

Факт №1. Между двумя трясинами нельзя пройди, если расстояние между центрами меньше суммарной длины радиусов.

Факт №2. Между границей леса и трясиной нельзя пройти, если расстояние между ними меньше радиуса.

Давайте построим граф, где вершины, это трясины и добавим ещё 4 вершины это границы леса, а рёбра между вершинами, если между ними нельзя пройти.

Тогда пройти из координаты (0, 0) нельзя дойти до $$$(n, m)$$$, если существует путь из левой границы леса до нижней или правой, или существует путь из верхней границы до нижней или правой.

Существование такого пути можно проверить обычным dfs.