|
Дистанционный практикум по программированию
|
||||||||||
|
|
|||||||||||
| Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь. |
12. Быстрое питание
|
| Статистика | Послать на проверку | Задачу добавил debug |
|
Фастфуд-сеть McBurger включает n ресторанов, расположенных вдоль автострады. Недавно владельцы решили построить k складов (k ≤ n), каждый из которых будет размещаться на базе одного из ресторанов (в том же здании, что и ресторан). Каждый склад будет обеспечивать продуктами ресторан, в здании которого он находится, а также некоторые другие рестораны, для которых этот склад будет являться ближайшим. Требуется написать программу, которая определит оптимальное расположение складов. Критерий оптимальности: сумма расстояний от каждого ресторана до ближайшего к нему склада должна быть наименьшей. Входные данные Во входных данных содержится описание нескольких фастфуд-сетей. Каждое описание начинается со строки, содержащей два целых числа n и k, где n – число ресторанов, k – число складов (1 ≤ n ≤ 200, 1 ≤ k ≤ n). Затем идут n строк, содержащих по одному целому числу – позиции di ресторанов от начала автострады в порядке возрастания. Все позиции лежат в диапазоне от -100000 до 100000. Входные данные заканчивается, когда 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 |
| Задачи с соревнований и сборов / | Школьные олимпиады и курсы Вологодской области / | Импульс, смена 2019 / | Динамическое программирование / |
| 2. 11 - Дерево поиска | 12. | 291. 13 - Триангуляция |
| Задачи с соревнований и сборов / | Школьные олимпиады и курсы Вологодской области / | Импульс, сентябрь 2020 / | Импульс-2020, ДП / |
| 870. 08 - Куча камней - 2 | 12. |
| время генерации 0.469 сек. | |
| © Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А. |