АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

12. Быстрое питание

Ограничение времени: 1 сек.
Ограничение памяти:65536 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил debug

Фастфуд-цепочка McBurger включает несколько ресторанов, расположенных вдоль автострады. Недавно владельцы решили построить несколько складов, каждый из которых будет размещён на базе какого-то из ресторанов и обеспечит несколько ближайших ресторанов нужными продуктами. Требуется написать программу, которая определит оптимальные позиции и назначения складов.

Вам даются позиции n ресторанов вдоль автострады в виде n целых чисел d1 < d2 < ... < dn (di - это расстояния, отмеренные от штаб-квартиры компании, которая тоже находится на автостраде). Также вам даётся число k (k<=n) - количество складов, которое нужно построить.

Данные k складов должны быть построены в k различных точках на автостраде, в которых уже стоят какие-то рестораны. Каждому ресторану назначается ближайший к нему склад, из которого он будет снабжаться. Чтобы минимизировать затраты, суммарная дистанция, определяемая как

должна быть минимально возможной.

Напишите программу, определяющую позиции k складов, при которых суммарное расстояние будет минимальным

Исходные данные

Входной файл содержит несколько описаний фастфуд-цепочек. Каждое описание начинается со строки, содержащей два целых числа n and k, где 1<=n<=200, 1<=k<=30, k<=n. Далее идут n строк, содержащих по одному целому числу - позиции di ресторанов в порядке возрастания.

Входной файл заканчивается, когда в очередном описании n=k=0. Эти данные обрабатывать не требуется.

Результат

Для каждой фастфуд-цепочки выведите строку, содержащую суммарное расстояние (как описывается в тексте задачи) и пустую строку после него.

Пример

Исходные данныеРезультат
6 3
5
6
12
19
20
27
0 0
8

Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи по темам / Динамическое прогр-е, рекуррентные соотношения /
873. Tower of Hanoi 12. 1717. Возрастающая подпоследовательность 67. Восстановление скобок 14. Выражение
Задачи с соревнований / Тренировки ВоГУ / ВоГТУ и ВоГПУ 17.11.2007 /
479. E - Sorting Slides 12. 480. G - Prime Cuts 481. H - Uniform Generator
 
время генерации 0.109 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.