Олимпиадный тренинг

Задача . Два мусоровоза 2


Задача

Темы:
На каждом километре кольцевой автодороги с двусторонним движением установлены контейнеры для мусора. Длина кольцевой автодороги равна N километров. Нулевой километр и N-й километр автодороги находятся в одной точке. Известно количество мусора, которое накапливается ежедневно в каждом из контейнеров.
На автодороге работают два мусоровоза. Один едет по часовой стрелке, другой против. Оба мусоровоза выезжают из центра переработки одновременно навстречу друг другу и встречаются возле одного из контейнеров. Из одного контейнера вывезти мусор может только один мусоровоз. Время доставки мусора вычисляется как произведение количества мусора на расстояние от пункта до центра переработки. Центр переработки отходов открыли в одном из пунктов сбора мусора таким образом, чтобы общее время сбора мусора двумя мусоровозами было минимально.
Определите, возле контейнера с каким номером необходимо поставить центр переработки, чтобы потребовалось минимальное время мусоровозам для сбора мусора.

Входные данные
Дано два входных файла (файл A и файл B), каждый из которых в первой строке содержит число N (1 <= N <= 10 000 000) – количество пунктов сбора мусора на кольцевой автодороге. В каждой из следующих N строк находится число – количество мусора в контейнере (все числа натуральные, количество мусора в каждом пункте не превышает 1000). Числа указаны в порядке расположения контейнеров на автомагистрали, начиная с первого километра.
В ответе укажите два числа: сначала значение искомой величины для файла А, затем – для файла B через пробел.

Типовой пример организации данных во входном файле
7
8
20
5
13
7
19
21


При таких исходных данных необходимо открыть центр переработки возле контейнера с номером 7:
Первый мусоровоз собирает мусор: 0 * 21 + 1 * 19 + 2 * 7 + 3 * 13 = 72
Второй мусоровоз потратит времени: 0 * 21 + 8 * 1 + 20 * 2 + 3 * 5 = 63
Итоговое время, которое потратят два мусоровоза: 72
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий время для всех возможных
вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.

 
 

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
Комментарий учителя