Олимпиадный тренинг

Задача . 26-18042026-1


Задача

Темы:

Вдоль туристического маршрута длиной 20 км расположены смотровые площадки и объекты показа. Туристические агентства подают заявки на проведение экскурсий. В каждой заявке указано, с какой точки (в метрах от начала маршрута) начинается экскурсия и какова её протяжённость (в метрах).

Если маршруты двух или более экскурсий имеют общую часть пути, то одновременно можно проводить не более одной из таких экскурсий (чтобы группы не мешали друг другу). Если конец одного маршрута совпадает с началом другого, то обе экскурсии можно проводить — они не пересекаются.

Определите наибольшее количество экскурсий, которые можно провести одновременно, и в этом случае минимальную длину неохваченного участка в конце маршрута (в метрах).

Входные данные

Первая строка входного файла содержит целое число N (N ⩽ 2000) — количество заявок на проведение экскурсий. Следующие N строк содержат пары чисел, обозначающих начало маршрута (в метрах от начала пути) и его протяжённость. Каждое из чисел натуральное, не превосходящее 20 000. Гарантируется, что конец маршрута не выходит за пределы пути.

Выходные данные

В ответе запишите два целых числа: сначала наибольшее количество экскурсий, которые можно провести одновременно, затем — минимально возможную при таком количестве заявок длину неохваченного участка в конце маршрута (в метрах).

Типовой пример:

5
1 2000
2001 3000
10001 6000
17001 2000
16001 3000

При таких исходных данных будет выполнено не более 4 заявок. Могут быть выполнены заявки с номерами 1, 2, 3 и 4 или заявки с номерами 1, 2, 3 и 5.

Ответ: 4 999


Статистика успешных решений по компиляторам