Описание

Ограничение по времени: 500 ms
Ограничение по памяти: 256 Mb

Ответы на вопросы

Задача: Circular Barn

У Фермера Джона круглый амбар. Амбар состоит из кольца из n комнат, пронумерованных 1…n по периметру (3≤n≤1,000). Каждая комната имеет двери в две соседние комнаты и одну дверь во внешний мир.
ФД хочет разместить ровно ri коров в комнате i (1≤ri≤1,000,000). Он планирует открыть k внешних дверей (1≤k≤7), через которые коровы будут входить в амбар. Каждая корова затем идёт по часовой стрелке, пока не добредёт до нужной комнаты. ФД хочет открыть двери так, чтобы все коровы вместе прошли как можно меньшее расстояние. Коровы предварительно могут собраться как им выгоднее перед этими незакрытыми дверями (эти перемещения не входят в общее расстояние, учитываемое в задаче). Определите минимальное суммарное расстояние, которое придётся пройти коровам, если ФД наилучшим образом выберет какие k открыть.
 
ФОРМАТ ВВОДА:
Первая строка ввода содержит n и k. Последующие n строк содержат r1…rn.

ФОРМАТ ВВОДА:
Выведите минимальное суммарное расстояние пройденное коровами.

Ввод Вывод
6 2
2
5
4
2
6
2
14


ФД может открыть двери 2 и 5. 11 коров войдут в двери 2 и пройдут суммарное расстояние 8 чтобы попасть в комнаты 2,3,4. 10 коров войдут в дверь 5 и пройдут общее расстояние 6, чтобы попасть в комнаты 5,6,1.



 


Прикрепите файл с исходным кодом программы:
     
или введите исходный код на языке:


Правила оформления программ и список ошибок при автоматической проверке задач
           

Ваш ответ:

Загруженные файлы:


Нет

Примечание учителя: