Видео не загрузилось
Похоже, vkvideo.ru недоступен из вашей сети (VPN, файрвол или блокировка провайдера).
Варианты
Тренажёр
Секундомер
00:00.00
15–25 мин
26 2027-Анисимов-2
Вдоль дороги длиной 12 км расположены дома.
В течение дня жители отправляют в управляющую компанию заявки на уборку снега.
В каждой заявке указано, с какой точки (в метрах от начала дороги) нужно начать уборку и какова длина участка (в метрах), который требуется очистить.
Если участки дороги в двух или более заявках имеют общую часть дороги, то можно выполнить не более одной из таких заявок.
Если конец одного участка совпадает с началом другого, то нужно убрать оба участка.
Определите, наибольшее количество заявок, которые может выполнить управляющая компания, и в этом случае минимальную длину неубранного участка, расположенного в конце дороги (в метрах).
Входные данные Первая строка входного файла содержит целое число N (N ⩽ 2000) - количество заявок на уборку снега.
Следующие N строк содержат пары чисел, обозначающих начало участка (в метрах от начала дороги) и его протяжённость.
Каждое из чисел натуральное, не превосходящее 12 000.
Гарантируется, что конец участка не выходит за пределы дороги.
В ответе запишите два целых числа: сначала наибольшее количество заявок, которые может выполнить управляющая компания, затем - минимально возможную при таком количестве заявок длину неубранного участка, расположенного конце дороги (в метрах).
Типовой пример организации данных во входном файле 5 1 1000 1001 1000 2001 2500 4501 500 4501 1500 При таких исходных данных будет выполнено не более 4 заявок.
Могут быть выполнены заявки с номерами 1, 2, 3 и 4 или заявки с номерами 1, 2, 3 и 5.
Ответ: 4 5999.
Время решения
00:00.00
Нажмите «Пуск», когда начнёте решать
Пробел — пуск и пауза
Цель - 0
на сайте - 0 дней
Прогноз 0