|
На каждом 3-м километре кольцевой автодороги с двусторонним движением установлены контейнеры для мусора. Длина кольцевой автодороги равна 3
N
километров. Нулевой километр и 3
N
-й километр автодороги находятся в одной точке. Известно количество мусора, которое накапливается ежедневно в каждом из контейнеров. Из каждого пункта мусор вывозит отдельный мусоровоз. Стоимость доставки мусора вычисляется как произведение количества мусора на расстояние от пункта до центра переработки. Центр переработки отходов расположен в одном из пунктов сбора мусора таким образом, что общая стоимость доставки мусора из всех пунктов минимальна.
Определите минимальную суммарную стоимость доставки мусора из всех пунктов сбора в центр переработки отходов.
Входные данные
Дано два входных файла (файл
A
и файл
B
), каждый из которых
в первой строке содержит число
N
(1 ≤
N
≤ 10 000 000)
–
–
количество пунктов сбора мусора на кольцевой автодороге. В каждой из следующих
N
строк находится число
–
–
количество мусора в контейнере (все числа натуральные, количество мусора в каждом пункте не превышает 1000). Числа указаны в порядке расположения контейнеров на автомагистрали, начиная с первого километра.
В ответе укажите два числа: сначала значение искомой величины для файла
А
, затем
–
–
для файла
B
.
Типовой пример организации данных во входном файле
6
8
20
5
13
7
19
При таких исходных данных, если контейнеры установлены на каждом километре автодороги, необходимо открыть центр переработки в пункте 6. В этом случае сумма транспортных затрат составит:
1
�
�
7 + 0
�
�
19 + 1
�
�
8 + 2
�
�
20 + 3
�
�
5 + 2
�
�
13.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Предупреждение:
для обработки файла
B
не следует
использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
|