По мотивам задачи: Пробник ИМЦ СПб (Уровень: B) (kompege =6638, silvertests=46427)
Для решение задачи желательно использовать "префикс-метод"
В задание используются последовательности длиной до 5*106 элементов.
В некоторой стране построен радиотелескоп. Антенны телескопа расположены вдоль шоссе.
Номер антенны соответствует километровой отметке от начала шоссе. Каждая антенна в сутки принимает
определённое количество сигналов, формирует их в пакеты и отправляет пакеты в Центр обработки.
Центр обработки разместили рядом с одной из антенн так, чтобы количество энергии,
расходуемой на передачу данных от всех антенн, было минимальным.
Количество энергии, необходимое для передачи всех пакетов с данными, равно
произведению расстояния от антенны до центре обработки на количество передаваемых пакетов с данными.
Ваша задача: написать функцию, которая принимает список с описанием антенн и возвращает
оптимальное положение для Центра обработки. Это номер антенны, рядом с которой следует
разместить центр обработки данных. Если таких номеров несколько, укажите наименьший из них.
| Пример входного списка: |
Ожидаемый результат |
Пояснение |
|
(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 |
Входные данные:
Список, состояший из кортежей. Каждый кортеж содержит два натуральных числа:
- номер антенны и количество пакетов, отправленных антенной в Центром обработки.
Антенны нумеруются в порядке их расположения вдоль шоссе, начиная с нулевой отметки.
Выходные данные:
Кортеж из двух натуральных чисел: сначала искомый номер антенны, затем суммарную энергию.