|
Дистанционный практикум по программированию
|
||||||||||
|
|
|||||||||||
| Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь. |
1937. Камеры
|
| Статистика | Послать на проверку | Задачу добавил debug |
|
Между пунктами А и Б имеется автодорога. В некоторых точках вдоль неё установлено N камер контроля скорости. В связи с завершением строительства ещё одной дороги компания, которой принадлежат камеры, приняла решение снять K из них и переместить на новую дорогу. Осталось выбрать, какие именно камеры следует снять. Посовещавшись, эксперты компании решили, что наилучшим вариантом будет снять такие K камер, чтобы расстояние между двумя самыми близкими друг к другу оставшимися камерами получилось как можно больше. Определите, какие именно камеры следует снять в соответствии с данным критерием. Входные данные В первой строке входных данных записано целое число N – количество камер. Во второй строке записано целое число K – сколько камер нужно снять. В следующих N строках записаны N целых чисел в диапазоне от 0 до 109 – координаты камер. Координаты даны в порядке возрастания без повторений. Выходные данные В первую строку выведите одно целое число – максимально возможное расстояние между ближайшими друг к другу оставшимися камерами. Во вторую строку выведите K различных целых чисел – номера камер, которые нужно снять. Нумерация начинается с единицы. Номера можно выводить в любом порядке. Если есть несколько верных ответов, выведите любой. Система оценки Подзадача 1 (до 50 баллов): 3 ≤ N ≤ 105, K = 1 Подзадача 2 (до 25 баллов): 3 ≤ N ≤ 20, 1 < K ≤ N - 2 Подзадача 3 (до 25 баллов): 3 ≤ N ≤ 105, 1 < K ≤ N - 2 Примеры Входные данные 4 1 40 50 60 80 Выходные данные 20 2 Входные данные 5 3 10 20 40 50 80 Выходные данные 70 2 3 4 Примечание В первом примере можно убрать камеру номер 2 (с координатой 50). Тогда ближайшие друг к другу оставшиеся камеры будут находиться на расстоянии 20. Во втором примере нужно убрать все камеры, кроме первой и последней. Тогда между оставшимися будет расстояние 70. |
| Статистика | Послать на проверку | Обсуждение задачи | Автор/источник: |
| Задачи с соревнований и сборов / | Школьные олимпиады и курсы Вологодской области / | ВсОШ, муниципальные этапы / | Муниципальный этап 2019-2020 / | Классы 9-11 / |
| 1936. 4 - Полоска | 1937. |
| время генерации 0.11 сек. | |
| © Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А. |