← вернуться к уроку · Практика: Жадные идеи и их ловушки
Накрыть точки
5000 мс · 256 МБ · всё или ничего
На прямой отмечены точек с целыми координатами. Их нужно накрыть отрезками длины ровно ; отрезки можно располагать где угодно, в том числе с нецелыми концами.
Какое наименьшее число отрезков понадобится?
Формат ввода
В первой строке числа от до и от до . Во второй — координат от до в произвольном порядке.
Формат вывода
Одно число.
Примеры
ввод
4 2 1 2 3 9
вывод
2
Примечание
Самую левую непокрытую точку выгодно ставить в самое начало нового отрезка.
Войдите, чтобы отправлять решения.