23/04/2024 23:42:26

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

939. Армия страдает бессонницей

Ограничения: время – 1s/2s, память – 16MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Новая система поставок для армии от разных подрядчиков породила неожиданную проблему. Походные кровати двенадцати разных производителей оказались сильно отличающимися по размерам. В связи с чем встал вопрос – какие из (уже занесенных в казармы!) кроватей необходимо убрать, чтобы ни одна из них не мешала другой, но кроватей в казарме осталось максимальное количество. А пока генералы решают данный вопрос, солдаты вынуждены обходиться без сна в казармах. Так что времени на перемещение кроватей нет! Необходимо только убрать ненужные кровати и посчитать максимальное количество не залезающих друг на друга оставшихся кроватей. Кстати, как известно казармы нового образца настолько узкие, что все кровати стоят в одну линию.

Ввод

Первая строка – числа `N` (количество кроватей, `1\ ≤\ N\ ≤\ 100000`) и `M` (минимальная длина кровати, которую нужно рассматривать, `M\ ≥\ 1`, иными словами `M` – минимальная длина кровати, необходимая солдату для сна).Следующие `N` строк – пары чисел [`A,B`] (`0\ <\ A\ <\ B`), задающие координаты кровати на прямой.

Вывод

Максимальное число непересекающихся друг с другом кроватей, длина каждой из которых `≥\ M`. Касание кроватей разрешено.

Пример ввода

Пример вывода

Источник: Турнир "Экспонента-2008"

03/07/2008	Лето 2008 дорешивание ( 2D)
04/07/2008	Лето 2008 - 2 (D)