ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Турниры > Алгоритмы и структуры данных — 2019. Набор задач 2 > задача:


F. Ларьки

Алгоритмы и структуры данных — 2019. Набор задач 2

Старт: 18.сен.2022 в 13:10:00
Финиш: 29.дек.2022 в 13:10:00
Турнир завершён!
• Турнирная таблица

Задачи турнира

• Подсказки к задачам
• A. Левый двоичный поиск
• B. Правый двоичный поиск
• C. Принтеры
• D. Забор
• E. Все любят уравнения
• F. Ларьки
• G. Лес и поле
• H. Станция

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/2000/2000/2000 мс. Лимит памяти 65536/65536/65536/65536 Кб.

Ларьки
Ларьки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

На главной улице олимпийской деревни расположились ларьки с сувенирами. Продавцы сувениров заметили, что из-за слишком близкого расположения некоторых ларьков уровень продаж в них заметно падает. Поэтому было решено переместить ларьки так, чтобы расстояние между любыми соседними ларьками было не меньше D.

Каждый из продавцов может передвинуть свой ларёк влево или вправо по улице со скоростью 1 метр в минуту. Перемещения всех ларьков осуществляются независимо. Определите, какое наименьшее время понадобится для того, чтобы расположить все ларьки требуемым образом.

Входные данные

Первая строка содержит целые числа N и D (1 ≤ N ≤ 105, 1 ≤ D ≤ 1000) — соответственно количество ларьков и требуемое минимальное расстояние между соседними ларьками.

Вторая строка содержит N целых чисел Xi ( - 100 ≤ Xi ≤ 100) — координаты ларьков в метрах.

Выходные данные

Выведите одно вещественное число с точностью не менее 3 знаков после запятой — минимальное время в минутах, требуемое для расположения ларьков нужным образом.

Примеры

Входные данные
4 2
11 9 15 11
Выходные данные
1.000000
Входные данные
4 1
5 5 5 5
Выходные данные
1.500000
Для отправки решений необходимо выполнить вход.

www.contester.ru