Статья Автор: Лебедев Дмитрий

ЕГЭ_27_Телескопы вдоль шоссе_Поиск и разбор решения. Часть 2

Z-функция. Префикс-функция

Телескопы вдоль шоссе (ЕГЭ 27-2022). Поиск и разбор решения. Часть 2.
По мотивам задачи: Пробник ИМЦ СПб 
Часть 1. Тетрадь 51148


В некоторой стране построен радиотелескоп. Антенны телескопа расположены вдоль шоссе. 
Номер антенны соответствует километровой отметке от начала шоссе. Каждая антенна в сутки принимает
определённое количество сигналов, формирует их в пакеты и отправляет пакеты в Центр обработки.
Центр обработки разместили рядом с одной из антенн так, чтобы количество энергии,
расходуемой на передачу данных от всех антенн, было минимальным.

Количество энергии, необходимое для передачи всех пакетов с данными, равно
произведению расстояния от антенны до центре обработки на количество передаваемых пакетов с данными.
Определите номер антенны, рядом с которой следует разместить центр обработки данных.
Если таких номеров несколько, укажите наименьший из них.

Пример входного файла: Ответ Пояснение

6
1 100
3 250
8 7
10 4
15 1
31 160

 3 4755 Для случая, когда центр обработки данных размещён около 3-й антенны,
суммарную энергию, необходимую для передачи данных,
можно оценить как
2·100 + 5·7 + 7·4 + 12·1 + 28·160 = 4755

Входные данные:

  • в первой строке число: количество антенн N .
  • Каждая из следующих N строк содержит два натуральных числа – номер антенны
    и количество пакетов, отправленных антенной в Центром обработки.
    Антенны нумеруются в порядке их расположения вдоль шоссе, начиная с нулевой отметки.

В ответе укажите два числа (в одной строке через пробел) : сначала искомый номер антенны, затем суммарную энергию.


Алгоритм II. Сокращаем время.

Если Вы разбирали часть 1, то легко догатались, что функция значений суммарной энергии похожа на параболу с ветвями, направленными вверх,
то есть вначале убывает, а затем возрастает. 
Тогда алгоритм может быть немного модифицирован (время сократим примерно в 2 раза)
  1. Чтение всех данных в список.
  2. Написание подпрограммы нахождения числа посылок для конкретного расположения центра о
  3. Перебор положения для Центтра обработки, до тех пор, пока не начнется "фаза подъема"
Это не именяет сложность алгоритма, но сокращает его раза в два. 

Заменим цикл for на цикл файл и опять построим графическое представление данных


Запустите программу несколько раз, попробуйте определить вид функции и предложить способы для повышения эффективности алгоритма
 

Алгоритм III. Выпуклые функции и тернарный поиск.
Легко заменить, что функция "суммы энергии" - это выпуклая функция.
Выпуклыми функциями являются чётные степенные (x2, x4, ...) и модульные (a|x-b|).
Известная теорема утверждает, что сумма выпуклых функций есть выпуклая функция.
Это и есть наш случай, значит функция "Суммарной энергии" есть выпуклая функция.
Для поиска точек экстремума выпуклых функций можно применить тернарный поиск.
В нашем случае необходимо найти такое j, что: Fj <  Fj -1и Fj <= Fj+1
( Fj - значение суммарной энергии при размещении Центра обработки в точке j)
Поскольку этот метод не является самым эффективным решением, то применим его в самом стандартном виде


Таким образом, решить задачу можно с помощью тернарного поиска.
Сложность алгоритма в этом случае будет O(N*log(N))
Используя этот способ попробуйте решить задачу на данных файла B  задачи 52149  (в файле более 106 записей)
Решение этой задачи с применение тернарного поиска требует не более 30 секунд процессорного времени
и может быть использовано на экзамене.
Код программы не более 30 операторов и его можно посмотреть здесь  
Однако, надо заметить, что данное решение не является наиболее эффективным
и в тетради  52150  будет продолжен поиск решения со сложностью O(N)

Прикрепленные файлы
27B_6638.txt
Пропустить Навигационные Ссылки.
Чтобы оставить комментарий нужна авторизация
Печать