Задача A. Рудольф и олимпиадное программирование Сначала требуется както сгенерировать рейтинги участников соревнований. Если последова тельно вычислять рейтинги всех участников, то решение не уложится по времени.
 Скачать 114.02 Kb.
|
|
Задания Регионального этапа Интеллектуальной олимпиады (номинация "Программирование") ПФО, декабрь 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 |