Для решения данной задачи нужно лишь аккуратно промоделировать действия из условия, а именно:
Прежде всего нам необходимо найти максимальное количество очков m на момент окончания игры. Это можно сделать эмулированием игры. Когда сыгран последний кон, мы можем перебрать всех игроков и найти максимальное количество очков. Далее, мы должны определить множество игроков, которые имеют максимальный балл в конце игры. Это делается в точности таким же способом, как и определение максимального количества баллов. Перебираем всех игроков в конце игры и сохраняем тех, у кого количество очков равно m. И наконец, нам нужно найти победителя. Для этого мы эмулируем игру еще раз и как только у игрока из списка победителей стало не менее m очков — мы нашли победителя!
Эта задача показывает, что иногда проще последовательно закодировать все написанное в условии, чем думать и оптимизировать.
A : C++ Code
Прежде всего, рассмотрим случай когда в матрице есть хотя бы одно число ноль. В этом случае мы легко можем найти путь со всего одним нулем в результирующем произведении — просто выведем любой путь с этим нулем. Этот путь не оптимален только в одном случае — когда существует путь вообще без концевых нулей. Поэтому заменим все числа 0 на числа 10 и решим задачу в общем случае. Если нашелся путь без концевых нулей — мы выберем его, в противном случае проходящий по нулю путь оптимален.
Итак, мы можем считать, что в матрице нет ни одного нуля. Давайте поймем, из чего получаются концевые нули в результирующем произведении. Если мы пойдем вдоль пути и будем считать количество множителей 2 и 5 в числах по пути, то количество концевых нулей будет min(количество 2, количество 5). Это позволяет нам решать задачу для 2 и 5 независимо. Итоговый ответ будет равен минимуму из независимых решений.
Теперь остался последний штрих — решить задачу для 2 и для 5. Новая интерпретация задачи выглядит следующим образом. Есть квадратная матрица с числами. Нам необходимо найти путь с минимальной суммой по ходу пути. Это классическая задача динамического программирования. Пусть A[r,c] — число в ячейке (r,c), а D[r.c] — ответ для данной ячейки. Тогда
D[r,c] = min(D[r-1,c],D[r,c-1]) + A[r][c]
B : C++ Code
Возьмем два стадиона и найдем множество точек, из которых стадионы видны под одинаковым углом. Не слишком сложные математические вычисления показывают, что это множество — прямая линия в случае, если стадионы имеют одинаковый радиус и это множество — окружность, если радиусы у стадионов различны. Пусть S(i,j) — множество точек, из которых стадионы i и j видны под одним углом. Т.к. по условию центры стадионов не находятся на одной прямой, то пересечение S(1,2) и S(1,3) сдержит не более, чем две точки. Если мы знаем эти две точки, то можем проверить, что они удовлетворяют условию и выбрать из них с максимальным углом обзора.
C : C++ Code
