HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Unsorted > problem:


Ларьки

Section problems

• Кот в рыбном магазине
• Красивые часы — 1
• Красивые часы — 2
• Кубок практики ИВТ
• Купим золото дорого
• Лабиринт
• Лабиринт
• Ларьки
• Ларьки
• Левый двоичный поиск
• Лес и поле
• Лесенка
• Лесенки
• Линейный поиск
• Листья
• Листья: валидатор
• Ломбард

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