HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Contests > Тренировочный турнир сезона «Зима — 2025» > problem:


H. Ларьки

Тренировочный турнир сезона «Зима — 2025»

Start: Feb.03.2025 at 10:00:00 AM
Finish: Mar.31.2025 at 11:00:00 PM
The contest is finished!
• Contest scoreboard

Contest problems

• A. Генерация приглашений
• B. Наименьшее и наибольшее
• C. Алёна и раунд
• D. Андреевский флаг
• E. Макс и распродажа в Steam
• F. Количество различных --- 3
• G. Оптимальная цена
• H. Ларьки
• I. Скобочная последовательность
• J. Макс и частичный период строки

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/2000/2000/2000 ms. Memory limit 65536/65536/65536/65536 Kb.

Ларьки
Ларьки
ограничение по времени на тест
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