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

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

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

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

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

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

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

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