EduBrick
← вернуться к уроку · Практика: Жадные идеи и их ловушки

Накрыть точки

5000 мс · 256 МБ · всё или ничего

На прямой отмечены nn точек с целыми координатами. Их нужно накрыть отрезками длины ровно LL; отрезки можно располагать где угодно, в том числе с нецелыми концами.

Какое наименьшее число отрезков понадобится?

Формат ввода

В первой строке числа nn от 11 до 21052 \cdot 10^5 и LL от 00 до 10910^9. Во второй — nn координат от 109-10^9 до 10910^9 в произвольном порядке.

Формат вывода

Одно число.

Примеры

ввод
4 2
1 2 3 9
вывод
2

Примечание

Самую левую непокрытую точку выгодно ставить в самое начало нового отрезка.

Войдите, чтобы отправлять решения.
← Вернуться к уроку