|
Remote Training on Programming
|
||||||||||
|
|
|||||||||||
| Hello, Guest! Please login or register. |
1937. Cameras
|
| View Problem Statistics | Submit | Problem added 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. |
| View Problem Statistics | Submit | Problem discussion | Author/source: |
| Problems from Contests and Camps / | School olympiads and couses of Vologda region / | All-Russian school olympiad, municipal stage / | Municipal Stage 2019-2020 / | Forms 9-11 / |
| 1936. 4 - Band | 1937. |
| time generating 0.125 sec. |
| © Copyright VSU, AVT, Nosov D.A., Andrianov I.A. |