Задание 26 ЕГЭ по информатике

Поезд следует по магистрали через $M$ населенных пунктов. Известно, что в поезде $K$ мест. Дан список из $N$ заявок на поездку, для каждой из которых известно, на какой станции пассажир собирается садиться, а на какой — выходить. При посадке на станции $Х$ контроллер отдает предпочтение тому пассажиру, который едет дальше остальных, определяя место пассажира, как свободное с минимальным номером (от 1 до $K$). При этом сначала осуществляется высадка пассажиров, а затем посадка.

Определите, сколько пассажиров смогут добраться до пункта своего назначения и сколько перегонов будут заняты все места поезда (перегон – участок магистрали между соседними населенными пунктами).

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

В первой строке файла задано три числа: $M$ ($2 ≤ M ≤ 2000$) – количество населенных пунктов со станциями на магистрали, $K$ ($1 ≤ K ≤ 1000$) – количество мест в поезде и $N$ ($1 ≤ N ≤ 10000$) – количество пассажиров, желающих проехать на поезде. В каждой из последующих $N$ строк располагаются пары чисел: сначала номер населенного пункта, откуда хочет начать свою поездку пассажир, затем номер населенного пункта, где пассажир собирается сойти с поезда.

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

Два числа: сначала количество пассажиров, которые смогут добраться до нужной им станции, затем количество перегонов, при прохождении которых в поезде будут заняты все места.

Типовой пример организации входных данных

10 3 6

2 6

2 4

3 5

3 8

4 9

4 6

При таких исходных данных добраться до нужного пункта смогут 4 пассажира ( (2, 6), (2, 4), (3, 8), (4, 9) ). При этом свободных мест не будет на перегонах 3 перегонах (3-4, 4-5 и 5-6).

Файл к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/9171_26.txt