Файл: Задача A. Рудольф и олимпиадное программирование Сначала требуется както сгенерировать рейтинги участников соревнований. Если последова тельно вычислять рейтинги всех участников, то решение не уложится по времени..pdf

Задания Регионального этапа Интеллектуальной олимпиады (номинация "Программирование")
ПФО, декабрь 2021 - март 2022 года
Задача A. Рудольф и олимпиадное программирование
Сначала требуется как-то сгенерировать рейтинги участников соревнований. Если последова- тельно вычислять рейтинги всех участников, то решение не уложится по времени. Но можно заме- тить, что различных рейтингов будет не более 3000. Тогда при генерации не более чем через 3000
итераций мы встретим рейтинг, который уже встречался в последовательности ранее. А так как рей- тинг следующего участника зависит только от предыдущего, значит значения в последовательности зациклятся. Тогда мы можем быстро посчитать, сколько полных циклов будет в последовательности,
и вычислить для каждого рейтинга, сколько участников с таким рейтингом будет в соревновании.
Назовем эту величину count id,r
, где id — номер соревнования, а r — рейтинг. Чтобы узнать ожида- емое место Рудольфа в соревновании, нужно посчитать сумму количеств участников с рейтингом выше рейтинга Рудольфа, то есть
P
3000
i=R+1
count id,i
, где R — текущий рейтинг Рудольфа. Теперь просто пройдем по всем соревнованиям и посчитаем эту информацию, обновляя рейтинг Рудольфа.
Для ответа на запросы нужно уметь быстро пересчитывать результаты соревнований.
Можно для каждого соревнования id посчитать суффиксные суммы suf id на массиве count:
suf id,r
= suf id,r+1
+ count id,r
. Тогда число участников с рейтингов выше Рудольфа R будет хра- ниться в suf id,R+1
. При дисквалификации участника из соревнования id мы пересчитываем suf id
,
а затем быстро пересчитываем рейтинг по всей цепочке соревнований. Итоговая асимптотика
O(3000 · (N + Q)).
Задача B. Рудольф и ёлка
Нужно перебрать все углы поворота от 0 до 359, пройтись по каждому уровню и повернуть все точки на текущий угол по формулам x = x·cos(alpha)−y ·sin(alpha), y = x·sin(alpha)+y ·cos(alpha).
Среди вершин уровня найти самую верхнюю, нижнюю, левую и правую координаты. Вычесть из верхней координаты нижнюю, чтобы найти высоту многоугольника, вычесть из правой координаты левую, чтобы найти ширину. Найти максимум из высот и широт всех многоугольников. Из макси- мальной высоты вычесть высоту двери, из максимальной ширины вычесть ширину двери. Сумма этих чисел будет ответом для текущего угла поворота. Взять минимальный ответ из всех углов.
Задача C. Рудольф и тигриная шкура
Каждая полоса начинается и заканчивается за пределами поля, и дырка не касается границ поля. Поэтому достаточно посмотреть все граничные клетки, посчитать в них количество звездочек и поделить на два. Это и будет ответом, так как каждая полоса имеет одно начало и один конец на границе поля.
Задача D. Рудольф и игра
В данной задаче необходимо последовательно вычислить итоговое количество солдат в армии.
Для каждого блокпоста союзников мы прибавляем к текущему размеру армии максимальное ко- личество солдат из доступных за дверьми. Для каждого вражеского блокпоста мы вычитаем из текущего размера армии минимальное количество солдат из доступных за дверьми. Если в какой- то момент размер нашей армии стал меньше или равен 0, то выводим «NO». Если мы прошли все блокпосты с положительным размером армии, то считаем максимальное количество уровней пира- миды level max
= b
√
army_sizec. Если это количество больше или равно заданной высоты H, то выводим «YES». В противном случае выводим «NO».
Страница 1 из 1