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

Разделы > Неотсортированные > задача:


Ларьки

Задачи раздела

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

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

Если у вас есть предложения или пожелания по работе 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