Статья Автор: Красильников Арсений

Решение задачи ЕГЭ 27 "По мотивам пробника ИМЦ СПБ"

Задание 27 ЕГЭ по информатике состоит из двух пунктов, первый из которых можно решить с помощью классического перебора, а для второго задумано создание оптимизированного решения.
Переборное решение является важным фактором для правильного решения этого типа задач, поскольку оно должно выдавать 100% правильный результат для сверки результата работы оптимизированного алгоритма. Поэтому переборный алгоритм должен быть логичным и абсолютно прозрачным в плане работы.
Здесь разберем решения задачи 51149.

1/ Переборное решение (асимптотика O(N^2))
Суть алгоритма: вычисление суммы для каждой антенны и после окончания вычисления сопоставление ее с текущей минимальной суммой. Если полученная сумма минимальна, сохраняем ее в переменную минимальной суммы и записываем номер антенны. 


• Интересный и важный факт задачи
Визуализируем значения суммы пакетов относительно i-й антенны.
Введите в поле ввода значение n - количества антенн и gap - верхней границы промежутка, в котором будут распределяться количества пакетов для каждой из антенн.


Можем заметить, что значения суммы для каждой из антенн образуют параболу, ветви которой направлены вверх. Таким образом, чтобы получить ответ, надо искать минимум этой параболы.

1.1/ "Крутой" переборный алгоритм (асимптотика O(N^2)). 
Основная крутость алгоритма заключается в том, что он, во-первых, отображает текущий ответ программы, во-вторых, написан на C++. Поскольку C++ значительно быстрее Python (принято считать, что Python медленнее в 25-30 раз) , но это значение сугубо зависит от поставленной задачи) и ответ выводится в режиме реального времени (как только был подсчитан), мы можем использовать такой переборный вариант на случай ядерной войны, если не сможем найти оптимизированное решение.
Мы знаем, что надо искать минимум параболы, поэтому можем прервать перебор сразу после того, как найденная сумма будет больше, чем минимальная. При больших входных данных, прерывание работы программы произойдет где-то на середине «шоссе» входных данных (см. график в «Интересный и важный факт задачи»), что позволит сократить время выполнения.


Если не получается запустить блок кода в Silvertests, скопируйте его и воспроизведите на своем компьютере. 


2/ Решение "А почему бы и нет" - поиск минимума парабола с помощью тернарного поиска (асимптотика O(N*log(N))).
Беря во внимание тот факт, что у нас образуется парабола с ветвями вверх, можем найти ее минимум с помощью тернарного поиска.


3/ Наиболее оптимальное решение через префиксные суммы (асимптотика O(N)). 
Пусть S – сумма всех пакетов, Si- - префиксная сумма всех пакетов до i невключительно, Si+ - префиксная сумма всех пакетов после i, включая i, Spi- – сумма пакетов до i, Spi+ - сумма пакетов после i.
Тогда:
Si+ = SSi-
Spi- = Sp(i-1)- + Si-
Spi+ = Sp(i-1)+ - Si+ = Sp(i-1)+ S + Si-
Получаем:
f(i) = Spi- + Spi+ = Spi- + Spi+ + 2Si- - S = f(i-1) + 2Si- - S
Учитывая, что f(i) – парабола с ветвями вверх, то нам нужно найти такие Si- и S, что выполняется:
2S(i – 1)- < S и 2Si- >= S одновременно.
Итого нам надо искать первое i такое, что 2Si- >= S


• Экзаменационные версии решений, предложенных выше

1/ Переборный алгоритм.


1.1/ "Крутой" переборный алгоритм.


2/ Решение "А почему бы и нет" - поиск минимума параболы с помощью тернарного поиска.


3/ Наиболее оптимальное решение через префиксные суммы.

Прикрепленные файлы
27A_6638.txt
27B_6638.txt
Печать