Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
RKAD
Вокруг города эльфов Ривенделла проложена кольцевая дорога – РКАД. Протяжённость её – N эльфийских ярдов. Вдоль дороги стоят эльфоярдовые столбы-порталы: они пронумерованы с 1, за столбом с номером N следует первый, расстояние между столбами, естественно, один эльфийский ярд.
В связи с возросшей активностью орков жители ЗаРКАДья решили перебраться в Ривенделл. Они выходили из дебрей и собирались у магических эльфоярдовых столбов, где и ожидали, когда их телепортируют в город.
Владыка Элронд решил осуществить транспортирвку эльфов так: он выйдет к одному из столбов, прикоснётся к нему – и там окажутся все стоявшие у столбов эльфы. Оттуда их доставка в город будет осуществляться без помощи магии (автобусами). Но вот сбор эльфов к одному столбу потребует существенных затрат магической энергии: затраты на транспортировку одного эльфа в эльфийских Джоулях равняются кратчайшему расстоянию в эльфийских ярдах по РКАД от столба, где эльф, до столба, где Элронд.
Разработайте программу, вычисляющую минимальные энергозатраты Элронда на транспортировку всех эльфов.
Входные данные. В первой строке значение N – количество столбов
на РКАД (их не более 50000), далее следуют N строк, в каждой из
которых целое неотрицательное число не больше 100 – количество эльфов у очередного столба.
Выходные данные. Одно целое число – минимальные возможные энергозатраты Элронда на транспортировку эльфов.
Для отправки решений необходимо выполнить вход.
|