Codeforces Beta Round #2 Разбор

Revision ru1, by Simple_Genius, 2016-01-25 16:54:05

Для решения данной задачи нужно лишь аккуратно промоделировать действия из условия, а именно:

Прежде всего нам необходимо найти максимальное количество очков m на момент окончания игры. Это можно сделать эмулированием игры. Когда сыгран последний кон, мы можем перебрать всех игроков и найти максимальное количество очков. Далее, мы должны определить множество игроков, которые имеют максимальный балл в конце игры. Это делается в точности таким же способом, как и определение максимального количества баллов. Перебираем всех игроков в конце игры и сохраняем тех, у кого количество очков равно m. И наконец, нам нужно найти победителя. Для этого мы эмулируем игру еще раз и как только у игрока из списка победителей стало не менее m очков — мы нашли победителя!

Эта задача показывает, что иногда проще последовательно закодировать все написанное в условии, чем думать и оптимизировать.

A : C++ Code

2B — Наименее круглый путь

Прежде всего, рассмотрим случай когда в матрице есть хотя бы одно число ноль. В этом случае мы легко можем найти путь со всего одним нулем в результирующем произведении — просто выведем любой путь с этим нулем. Этот путь не оптимален только в одном случае — когда существует путь вообще без концевых нулей. Поэтому заменим все числа 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

2C — Задача комментатора

Возьмем два стадиона и найдем множество точек, из которых стадионы видны под одинаковым углом. Не слишком сложные математические вычисления показывают, что это множество — прямая линия в случае, если стадионы имеют одинаковый радиус и это множество — окружность, если радиусы у стадионов различны. Пусть S(i,j) — множество точек, из которых стадионы i и j видны под одним углом. Т.к. по условию центры стадионов не находятся на одной прямой, то пересечение S(1,2) и S(1,3) сдержит не более, чем две точки. Если мы знаем эти две точки, то можем проверить, что они удовлетворяют условию и выбрать из них с максимальным углом обзора.

C : C++ Code

Tags codeforces beta round #2

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru2 Russian Simple_Genius 2016-01-25 16:54:50 21 Мелкая правка: '![ ](http://c' -> '[2A — Победитель](http://c'
ru1 Russian Simple_Genius 2016-01-25 16:54:05 3272 Разбор задач Codeforces beta round #2 (опубликовано)