Я распарсил. Click

2A — Победитель

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

Прежде всего нам необходимо найти максимальное количество очков 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

Пожалуйста, сообщайте о любых ошибок.

1А — Театральная площадь

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

Неприятности в этой задаче заключались в основном с типизацией и приоритетом вычислений, что очень сильно зависит от стиля кодирования и языка.

A : C++ Code

1B — Электронные таблицы

Отождестим буквенную запись столбца с числом в системе счисления с основанием 26. ('A' = 0, 'B'=1, 'Z' = 25). Тогда при переводе из буквенного обозначения в цифровое нужно к значению дополнительно добавить количество всех вариантов, имеющих меньшую длину, плюс один (ради формализма можно считать, что вариантов нулевой длины -- один, и отказаться от добавления единицы).

При переводе из цифрового обозначения в буквенное нужно сначала найти, сколько знаков понадобится и из числа вычесть количество обозначений меньшей длины (для чего последовательно вычитаем из числа количество обозначений, имеющих длину 0, потом количество имеющих длину 1, 2, и т.п., пока число не станет меньше, чем количество обозначений, имеющих текущую длину и следующее вычитание привело бы к появлению отрицательного числа), переводим в систему счисления 'A'..'Z'.

Возможна интерпретация, реализуемая более компактно, но там сложнее не допустить ошибку при реализации.

B : C++ Code

1C — Древнеберляндский цирк

Можно разбить на две подзадачи: найти центр правильного многоугольника и найти число углов.

Центр многоугольника обязан быть на одинаковом расстоянии от трех вершин. Можно воспользоваться обычным методом нахождения центра окружности, построенной по трем точкам. Напишу метод, которым воспользовался я. Для двух отрезков (x1,y1 — x2,y2) , (x2,y2 — x3,y3) находим среднюю точку, строим перпендикуляры, пересечение их даст искомый центр. Из подводные камни здесь: некоторые формулы в некоторых частных случаях дают деление на ноль. Лежать на одной прямой три точки из условия не могут (т.к. гарантируется корректность входных данных), а оставшийся плохой случаи можно устранить поворотом всей системы (т.е. всех трех точек) на случайно выбранный угол.

Нахождение числа углов

Поскольку при равном расстоянии от центра до вершины площадь правильного многоугольника возрастает монотонно с ростом N, можно просто перебирать все N, начиная с 3, и при нахождении первого подходящего печатать ответ и прекращать работу. Нужно, следовательно, для данного N уметь определять, могут ли данные вершины быть вершинами N-угольника -- критерий прост: углы между отрезками от центра до вершин должны быть кратны 2*pi/N. Воспользуемся свойством синуса: sin(x)=0, если аргумент кратен пи. Или можно с перебором написать ! Условие кратности угла между двумя отрезками заменяется при этом на следующее:

C : C++ Code

Всем доброго времени суток!

Я начал заниматься программированием в седьмом классе, сейчас я в восьмом. Раньше решал задачи на сайте acmp.ru( Школа Программиста ) и informatics.mccme.ru( Дистанционная подготовка ), сейчас же, с архива и тренировок на CodeForces И уделяю этому не мало времени. Но как вы можете заметить по моему рейтингу, прогресс довольно-таки маленький, точнее, его практически нету. В связи с этим, хотел бы услышать ваши мнения:

"Как начать эффективно заниматься ** Как прокачаться?** ?"

Заранее благодарю!!

I was trying to solve this problem from ICL2015div2 finals. I understand this is a problem on combinatorics (and perhaps DP) but I could not find a way towards solution.

Problem Link

I am weak in DP problems. They seem overwhelming to me most of the times. An elaborate explanations will surely be helpful for me. :)

Thanks in advance.