Информатика

(А. Рогов) В отделении банка используется система распознавания лиц, с помощью которой фиксируется время, когда посетитель пришел в отделение и время, когда он вышел. Для удобства время хранится как целое число, показывающее, сколько секунд прошло от начала суток до события. Посетителей банка обслуживают операторы, которые пронумерованы, начиная с 1. Посетитель обслуживается свободным оператором с минимальным номером. Оператор может принять следующего посетителя в ту же секунду, как обслуживаемый им посетитель покидает здание. На обслуживание требуется, как минимум, одна секунда. Если свободных операторов нет, посетитель становится в очередь. Посетитель может не дождаться своей очереди и уйти.

Определите, сколько посетителей было обслужено операторами и номер оператора, обслужившего последнего посетителя.

Входные данные представлены в файле 26-132.txt следующим образом. Первая строка входного файла содержит натуральное число N (1 ≤ N ≤ 10000) -- количество посетителей, и натуральное число K (1 ≤ K ≤ 1000) -- количество операторов в отделении. В каждой из последующих N строк записаны через пробел в возрастающем порядке по два целых неотрицательных числа: T₁ (0 ≤ T₁ ≤ 86399) -- время, в которое посетитель зашел в отделение и T₂ (T₁ ≤ T₂ ≤ 86399) -- время, когда он вышел. Считается, что до начала суток и после их окончания в помещении посетителей не было. Все, кто зашел в отделение, успел выйти до закрытия.

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

Пример входного файла:

6 2
1 50
2 40
5 100
50 86000
60 70
70 100

При таких исходных данных были успешно обслужены 4 посетителя, пятый и шестой ушли раньше, чем подошла их очередь. Последнего посетителя обслуживал оператор 1. Ответ: 4 1.

*(Е. Джобс) На въезде в город оборудована сельскохозяйственная ярмарка. Лотки для продажи стоят с двух сторон дороги с двусторонним движением. С каждой стороны расположено по К мест для торговли. Место бронируется на определенное количество минут, при этом управляющим ярмарки закладывается 15 минут на освобождение места после окончания его аренды. Места, которые расположены вдоль полосы по направлению в город, считаются наиболее прибыльными, поэтому при возможности занимаются в первую очередь. Если свободных мест нет, но новый продавец видит, что на одном из мест предыдущий продавец собирает вещи, то он встает в очередь за ним. При этом он не отличает сколько времени осталось на сбор, если несколько продавцов освобождают свое место. Поэтому встает в очередь за первым по номеру лотка. В случае, когда по направлению в город нет свободных мест, но есть места по направлению из города, продавец выбирает подождать собирающегося продавца с «прибыльной» стороны, если таковые имеются. Если на желаемое время мест нет и ни один из продавцов не собирается, то новый продавец уезжает с ярмарки.

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

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

Входные данные представлены в файле 26-131.txt следующим образом. Первая строка входного файла содержит натуральное число N (1 ≤ N ≤ 10000) -- количество потенциальных продавцов и натуральное число K (1 ≤ K ≤ 500) -- количество мест на каждой стороне дороги. В каждой из N следующих строк содержится два числа: Т (1 ≤ Т ≤ 4200) -- время от начала ярмарки в минутах, когда продавец планирует начать торговлю, и Р (1 ≤ Р ≤ 300) -- желаемое время аренды лотка.

Запишите в ответе два числа: количество продавцов, которые смогут арендовать место, и суммарную длительность аренды всех лотков вдоль стороны дороги по направлению в город.

Пример входного файла:

6 2
1 10
11 25
16 15
21 25
26 20
31 10

Обозначим лотки, как 1В и 2В (выгодный) со стороны в город, и 1Н, 2Н (невыгодный) -- из города. Тогда

1-й продавец: 1В -- 1-10 минут + 15 минут на сборы (лоток занят с 1 по 25 минуты)

2-й продавец: 2В -- 11-35 минут + 15 минут на сборы (лоток занят с 11 по 50 минуты)

3-й продавец: 1В -- дождаться, пока соберется предыдущий, 26-40 + 15 минут на сборы (лоток занят с 26 по 55 минуты)

4-й продавец: 1Н -- 21-45 + 15 минут на сборы (лоток занят с 21 по 60 минуты)

5-й продавец: 2Н -- 26-45 + 15 минут на сборы (лоток занят с 26 по 60 минуты)

6-й продавец уезжает с ярмарки

При этом все места с выгодной стороны будут заняты 40 минут (с 11 до 50). Ответ: 5 40.

Графически (с сеткой в 5 минут) можно представить работу ярмарки при таких входных данных следующим образом, где зеленый цвет - время торговли, желтый -- время сборов:

(ЕГЭ-2023) Система наблюдения ежеминутно фиксирует вход и выход посетителей магазина (в минутах, прошедших от начала суток). Считается, что в минуты фиксации входа и выхода посетитель находится в магазине. Нулевая минута соответствует моменту открытия магазина, который работает 24 ч в сутки без перерыва. Менеджер магазина анализирует данные системы наблюдения за прошедшие сутки, и выявляет отрезки времени наибольшей длины, в течение которых число посетителей, находящихся в магазине, не изменялось. Далее менеджер выбирает пики посещаемости -- промежутки времени, когда количество посетителей в магазине было наибольшим. Пиков посещаемости в течение суток может быть несколько.

Входной файл содержит время входа и выхода каждого посетителя магазина. Определите, сколько пиков посещаемости было в течение суток, и укажите число посетителей в момент пика посещаемости.

Входные данные представлены в файле 26-130.txt следующим образом. Первая строка входного файла содержит натуральное число N (1 ≤ N ≤ 10000) -- количество посетителей магазина. Следующие N строк содержат пары чисел, обозначающих соответственно время входа и время выхода посетителя (все числа натуральные, не превышающие 1440).

Запишите в ответе два натуральных числа: сначала найденное количество пиков посещаемости, а затем число посетителей в момент пика посещаемости.

Пример входного файла:

6
10 50
100 150
110 155
120 160
130 170
152 170

При таких исходных данных будет два пика посещаемости: с 130 по 150 минуту и с 152 по 155 минуту. Число посетителей в момент этих пиков равно 4. Ответ: 2 4.

(ЕГЭ-2023) На производстве штучных изделий N деталей должны быть отшлифованы и окрашены. Для каждой детали известно время её шлифовки и время окрашивания. Детали пронумерованы начиная с единицы. Параллельная обработка деталей не предусмотрена. На ленте транспортёра имеется N мест для каждой из N деталей. На ленте транспортёра детали располагают по следующему алгоритму:

-- все 2N чисел, обозначающих время окрашивания и шлифовки для N деталей, упорядочивают по возрастанию;

-- если минимальное число в этом упорядоченном списке -- это время шлифовки конкретной детали, то деталь размещают на ленте транспортёра на первое свободное место от её начала;

-- если минимальное число -- это время окрашивания, то деталь размещают на первое свободное место от конца ленты транспортёра

-- если число обозначает время окрашивания или шлифовки уже рассмотренной детали, то его не принимают во внимание.

Этот алгоритм применяется последовательно для размещения всех N деталей. Определите номер последней детали, для которой будет определено её место на ленте транспортёра, и количество деталей, которые будут отшлифованы до неё.

Входные данные представлены в файле 26-129.txt следующим образом. Первая строка входного файла содержит натуральное число N (1 ≤ N ≤ 1000) -- количество деталей. Следующие N строк содержат пары чисел, обозначающих соответственно время шлифовки и время окрашивания конкретной детали (все числа натуральные, различные).

Запишите в ответе два натуральных числа: сначала номер последней детали, для которой будет определено её место на ленте транспортёра, затем количество деталей, которые будут отшлифованы до неё.

Пример входного файла:

5
30 50
100 155
150 170
10 160
120 55

При таких исходных данных порядок расположения деталей на ленте транспортёра следующий: 4, 1, 2, 3, 5. Последней займёт своё место на ленте транспортёра деталь 3. При этом до неё будут отшлифованы три детали. Ответ: 3 3.

(ЕГЭ-2023) Входной файл содержит сведения о заявках на проведение занятий в конференц-зале. В каждой заявке указаны время начала и время окончания мероприятия (в минутах от начала суток). Если время начала одного мероприятия меньше времени окончания другого, то провести можно только одно из них. Если время окончания одного мероприятия совпадает с временем начала другого, то провести можно оба. Определите максимальное количество мероприятий, которое можно провести в конференц-зале и самое позднее время окончания последнего мероприятия.

Входные данные представлены в файле 26-128.txt следующим образом. Первая строка входного файла содержит натуральное число N (1 ≤ N ≤ 1000) -- количество заявок на проведение мероприятий. Следующие N строк содержат пары чисел, обозначающих время начала и время окончания мероприятий. Каждое из чисел натуральное, не превосходящее 1440.

Запишите в ответе два числа: максимальное количество мероприятий, которое можно провести в конференц-зале и самое позднее время окончания последнего мероприятия (в минутах от начала суток).

Пример входного файла:

5
10 150
100 110
131 170
131 180
120 130

При таких исходных данных можно провести максимум три мероприятия, например, по заявкам 2, 3 и 5. Конференц-зал освободится самое позднее на 180-й минуте, если состоятся мероприятия по заявкам 2, 4, 5. Ответ: 3 180.

(Е. Джобс) В волшебной стране живут гномы, которые любят варить зелья в магических котлах. Они имеют очень тонкую душевную организацию и стесняются стоять рядом с кем-то за соседним котлом. Гном всегда выбирает свободный котел с наименьшим номером, рядом с которым никто не стоит. Если это невозможно, но свободные котлы есть, гном выбирает свободный котел с наименьшим номером. Гном варит свою порцию зелья 6 минут, после чего уходит с поляны. В котле, который он освободил, другой гном сразу же может варить своё зелье.

Определите минимальное количество котлов, которых достаточно для того, чтобы каждый желающий гном сварил зелье, и количество гномов, которые не испытают неудобств, связанных с близким соседством при найденном количестве котлов. Считается, что гном испытывает неудобства, если при варке зелья стоит плечом к плечу с соседом хотя бы 1 минуту.

Входные данные представлены в файле 26-127.txt следующим образом. Первая строка входного файла содержит натуральное число N (1 ≤ N ≤ 10000) -- количество гномов, желающих сварить зелье. В каждой из следующих N строк записано время в минутах от начала суток, когда гном подошел к поляне с котлами -- натуральное число, не превышающее 1433. Строки в файле (кроме первой) расположены в случайном порядке.

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

Пример входного файла:

10
6
8
10
14
20
22

При таких исходных данных необходимо 3 котла. Зелье без неудобств смогут сварить два гнома, пришедших через 20 и 22 минуты после полуночи. Распределение котлов: 1 котёл: 6-12, 14-20, 20-26; 2 котёл: 10-16; 3 котёл: 8-14, 22-28. Ответ: 3 2.

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

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

Входные данные представлены в файле 26-126.txt следующим образом. Первая строка входного файла содержит три натуральных числа: 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). Ответ: 4 3.

(Д. Козлов) В одной волшебной местности живут гномы, которые любят варить зелья в магических котлах. Всего есть P котлов, они пронумерованы, в начальный момент все они свободны. Гномы варят зелья в порядке общей очереди. Первый в очереди гном, желающий сварить зелье, подходит к свободному котлу с наименьшим номером. Если котел ранее не использовался, гном может начать варить зелье сразу, а если уже использовался -- только через две минуты после того, как он подошел к такому котлу. Одна порция зелья варится 1 минуту.

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

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

Входные данные представлены в файле 26-125.txt следующим образом. Первая строка входного файла содержит два натуральных числа: D -- количество гномов (1 ≤ D ≤ 100000) и P -- количество котлов (1 ≤ P ≤ 1000). В каждой из последующих D строк содержится информация по одному гному: время подхода гнома к котлам (в минутах с начала суток) и количество имеющейся у него маны.

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

Пример входного файла:

5 2
1 6
4 9
3 1
4 5
9 11

При таких исходных данных за сутки было сварено 14 порций зелья. Наибольшее количество порций (5) было сварено гномом с количеством маны 11. Гном с количеством маны 1 сразу же уходит, т. к. у него недостаточно маны для заварки хотя бы одной порции зелья. Ответ: 14 5.

(Е. Джобс) На стадионе есть система предварительных заявок на покупку билетов на футбольный матч. Каждая заявка содержит одно число -- количество билетов, которые желает выкупить клиент. Утром перед матчем оператор распределяет заявки по следующему алгоритму:

1) Все билеты в одной заявке должны быть в одном ряду,

2) В первую очередь подтверждаются заявки с наибольшим количеством забронированных мест,

3) Места проверяются в порядке следования рядов, то есть оператор старается разместить все места из заявки в ряд с наименьшим номером, и при этом максимально близко к началу ряда.

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

Входные данные представлены в файле 26-124.txt следующим образом. Первая строка входного файла содержит три натуральных числа: количество рядов на стадионе K (1 ≤ K ≤ 1000), количество мест в одном ряду M (1 ≤ M ≤ 1000) и количество заявок N (1 ≤ K ≤ 20000). В каждой из N следующих строк записано одно натуральное число -- количество билетов в заявке.

В ответе запишите два числа: сначала количество подтвержденных заявок, затем количество оставшихся свободных мест на стадионе.

Пример входного файла:

3 20 7
8
15
10
17
13
6
4

При таких исходных данных оператор удовлетворит 5 заявок -- 15, 17, 13, 6 и 4 (всего 55 мест). На стадионе останется 5 свободных мест. Ответ: 5 5.

(А. Богданов) Проводится вычислительный эксперимент для определения необходимого количества самокатов на разных парковках города в начальный момент времени. Всего есть M парковок с номерами от 1 до М. Поступило всего N заявок на аренду самокатов. В каждой заявке указано время начала аренды в минутах от начала суток, продолжительность аренды, а также номера парковок старта и финиша. Определите сколько всего нужно самокатов, чтобы все заявки были выполнены, и какое наибольшее число самокатов в какой-то момент будут в аренде одновременно. Будем считать, что заряда самоката хватает на весь день и самокат может быть арендован со следующей минуты после окончания предыдущей аренды.

Входные данные представлены в файле 26-123.txt следующим образом. Первая строка входного файла содержит два натуральных числа, записанных через пробел: M (1 ≤ M ≤ 100) -- количество парковок, и N (1 ≤ N ≤ 10⁶) -- количество заявок. Каждая из N последующих строк описывает содержит четыре целых числа: время начала аренды в минутах от начала суток, длительность аренды в минутах, номер парковки старта и номер парковки финиша.

В ответе запишите два числа: сначала необходимое количество самокатов, затем наибольшее количество самокатов, которые в какой-то момент будут в аренде одновременно.

Пример входного файла:

2 3
1 4 2 2
3 6 1 1
5 9 1 2

При таких исходных данных нужно три самоката: два в начале размещаются на парковке 1 и один -- на парковке 2. Одновременно в аренде находятся максимум два самоката (с 3-й по 8-ю минуту включительно). Ответ: 3 2.

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

Входные данные представлены в файле 26-122.txt следующим образом. Первая строка входного файла содержит два натуральных числа, записанных через пробел: К (1 ≤ K ≤ 100) -- количество домиков в одной линии, и N (1 ≤ N ≤ 10⁶) - количество заявок. Каждая из N последующих строк описывает содержит два целых числа: час заезда и час выезда, считая от начала сезона.

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

Пример входного файла:

3 5
7 65
10 40
16 33
35 55
39 46

При таких исходных данных в линии по три домика. В первый день будут заселены все три домика первой линии. На следующий день заселят освободившийся дом на 1-й линии и один дом на 2-й линии. После 39 ч в отеле будет занято 4 домика. Ответ: 2 4.

(Д. Муфаззалов) На парковке расположены парковочные места для M категорий автомобилей. Номер категории -- целое неотрицательное число, меньшее, чем M. Для каждой категории автомобилей выделено некоторое количество парковочных мест. Приезжающий на парковку автомобиль занимает любое свободное место среди мест, предназначенных для автомобилей его категории, а также среди мест, предназначенных для автомобилей c бóльшим номером категории. Автомобиль всегда паркуется на подходящем свободном месте для автомобилей с наименьшей категорией. Если подходящего свободного места нет, автомобиль уезжает. Гарантируется, что никакие два автомобиля не приезжают одновременно. Если время прибытия автомобиля совпадает со временем окончания стоянки другого автомобиля, вновь прибывший автомобиль может занять освободившееся место, если оно подходит ему.

Пусть K -- минимальный номер категории парковочных мест, в которой за всё время припарковалось наибольшее количество автомобилей. Определите время, через которое освободятся (и больше не будут заняты) все парковочные места категории K, и количество автомобилей, которые парковались на местах категории K.

Входные данные представлены в файле 26-120.txt следующим образом. Первая строка входного файла содержит два натуральных числа, записанных через пробел: M -- количество категорий автомобилей, 1 ≤ M \< 525 600, и N -- общее количество автомобилей, приехавших на парковку в течение одного года, 0 ≤ N ≤ 10⁶. Вторая строка содержит M чисел -- количество парковочных мест на стоянке для автомобилей каждой категории, начиная с категории под номером 0, в порядке возрастания номеров категорий. Каждое из этих чисел не превышает 1000. Каждая из N последующих строк описывает один автомобиль и содержит три целых числа: время в минутах с начала года, когда автомобиль прибыл на парковку; необходимую длительность стоянки в минутах и номер категории автомобиля.

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

Пример входного файла:

2 5
2 1
5 22 0
8 30 1
14 15 0
25 12 0
20 40 1

При таких исходных данных: 1-й автомобиль (категории 0) припаркуется на месте категории 0 с 5 по 27 минуты, 2-й автомобиль (категории 1) припаркуется на месте категории 1 с 8 по 38 минуты,

3-й автомобиль (категории 0) припаркуется на месте категории 0 с 14 по 29 минуты, 4-й автомобиль (категории 0) не найдет место, 5-й автомобиль (категории 1) не найдет место. В категории мест с номером 0 припарковалось максимальное количество автомобилей -- 2, все парковочные места категории 0 освободились на 29-й минуте. Ответ: 29 2.

(Д. Муфаззалов) На парковке расположены парковочные места для M категорий автомобилей. Номер категории -- целое неотрицательное число, меньшее, чем M. Для каждой категории автомобилей выделено некоторое количество парковочных мест. Приезжающий на парковку автомобиль занимает любое свободное место среди мест, предназначенных для автомобилей его категории, а также среди мест, предназначенных для автомобилей c бóльшим номером категории. Автомобиль всегда паркуется на подходящем свободном месте для автомобилей с наименьшей категорией. Если подходящего свободного места нет, автомобиль уезжает. Гарантируется, что никакие два автомобиля не приезжают одновременно. Если время прибытия автомобиля совпадает со временем окончания стоянки другого автомобиля, вновь прибывший автомобиль может занять освободившееся место, если оно подходит ему.

Пусть K -- максимальный номер категории автомобилей, в которой за всё время припарковалось наибольшее количество автомобилей. Определите время, через которое освободятся (и больше не будут заняты) все парковочные места, предназначенные для категории автомобилей с номером K, и общее количество автомобилей всех категорий, которые уедут из-за отсутствия мест.

Входные данные представлены в файле 26-120.txt следующим образом. Первая строка входного файла содержит два натуральных числа, записанных через пробел: M -- количество категорий автомобилей, 1 ≤ M \< 525 600, и N -- общее количество автомобилей, приехавших на парковку в течение одного года, 0 ≤ N ≤ 10⁶. Вторая строка содержит M чисел -- количество парковочных мест на стоянке для автомобилей каждой категории, начиная с категории под номером 0, в порядке возрастания номеров категорий. Каждое из этих чисел не превышает 1000. Каждая из N последующих строк описывает один автомобиль и содержит три целых числа: время в минутах с начала года, когда автомобиль прибыл на парковку; необходимую длительность стоянки в минутах и номер категории автомобиля.

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

Пример входного файла:

2 5
2 1
5 22 0
8 30 1
14 15 0
25 12 0
20 40 1

При таких исходных данных: 1-й автомобиль (категории 0) припаркуется на месте категории 0 с 5 по 27 минуты, 2-й автомобиль (категории 1) припаркуется на месте категории 1 с 8 по 38 минуты,

3-й автомобиль (категории 0) припаркуется на месте категории 0 с 14 по 29 минуты, 4-й автомобиль (категории 0) не найдет место, 5-й автомобиль (категории 1) не найдет место. В максимальное количество припаркованных автомобилей (2) имели категорию 0, все парковочные места для автомобилей категории 0 (т. е. места категорий 0 и 1) освободились на 38-й минуте. Ответ: 38 2.

На парковке есть L мест для легковых автомобилей и M мест для микроавтобусов. Приезжающий на парковку автомобиль занимает любое подходящее свободное место, при этом легковой автомобиль может встать на свободное место, предназначенное для микроавтобуса, но микроавтобус не может занять место, предназначенное для легкового автомобиля. Если подходящего свободного места нет, автомобиль уезжает. Гарантируется, что никакие два автомобиля не приезжают одновременно. Если время прибытия автомобиля совпадает со временем окончания стоянки другого автомобиля, вновь прибывший автомобиль может занять освободившееся место, если оно подходит ему по типу.

Определите количество микроавтобусов, которые смогут припарковаться, и общее количество автомобилей (как легковых, так и микроавтобусов), которые уедут из-за отсутствия мест.

Входные данные представлены в файле 26-119.txt следующим образом. Первая строка входного файла содержит три целых числа: N -- общее количество автомобилей, приехавших на парковку в течение суток; L -- количество мест для легковых автомобилей и M -- количество мест для микроавтобусов. Каждая из следующих N строк описывает один автомобиль и содержит два целых числа и букву. Первое число означает время в минутах с начала суток, когда автомобиль прибыл на парковку, второе -- необходимую длительность стоянки в минутах. Буква означает тип автомобиля: A -- легковой, B -- микроавтобус.

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

Пример входного файла:

5 2 1
5 22 A
8 30 B
14 15 A
25 12 A
20 40 B

При таких исходных сумеет припарковаться только один микроавтобус, приехавший на 8-й минуте. Два автомобиля -- легковой на 25-й минуте и микроавтобус на 20-й -- уедут, не найдя место для парковки. Ответ: 1 2.

(М. Шагитов) В течение дня в магазине электроники каждые t минут, начиная с момента t, предлагается один товар со скидкой. В течение дня магазин посещает N клиентов, желающих приобрести товар со скидкой (по скидочной карте). Известны время прихода и ухода каждого клиента, а также число товаров, уже приобретенных ранее с использованием скидочной карты. Клиент может купить товар со скидкой, если он присутствует в магазине в момент начала продажи товара и он купил ранее по скидочной карте менее, чем M товаров. В случае, когда несколько клиентов могут купить товар, выбирается тот, кто до этого купил по скидочной карте меньше товаров. При равенстве количества товаров, преимущество получает тот, кто уходит позже. После покупки число купленных товаров на скидочной карте клиента увеличивается на один. На последней минуте, когда покупатель уходит из магазина, он также может купить скидочный товар.

Определите, сколько минут провёл в магазине покупатель, купивший наибольшее количество товаров со скидкой, и сколько товаров он приобрел.

Входные данные представлены в файле 26-118.txt следующим образом. Первая строка содержит три натуральных числа: t (1 ≤ t ≤ 1440) - интервал между продажами товаров, N (1 ≤ N ≤ 1000) -- количество покупателей, и M (1 ≤ M ≤ 10⁹) -- ограничение для скидки. В следующих N строках указаны три значения: минута прихода покупателя в магазин, минута ухода покупателя из магазина (натуральные числа, не превышающие 1440) и количество товаров, купленных ранее по скидочной карте (натуральное число, не превышающее 10⁹).

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

Пример входного файла:

10 5 4
5 50 3
1 30 2
10 56 1
4 40 3
20 40 2

При таких исходных данных товары для пришедших покупателей продавались в единственном экземпляре в минуты: 10, 20, 30, 40, 50. В итоге покупатель {10, 56, 1} купил наибольшее количество товаров -- 3 (на минутах 10, 20 и 40) и находился в магазине 47 минут (с 10 по 56-ю минуту). Покупатели {20, 40, 2} и {5, 50, 3} купили только один товар каждый (на минутах 30 и 50 соответственно), а остальные покупатели не смогли ничего приобрести. Ответ: 47 3.

(А. Богданов) В гостинице составляют недельный план уборки номеров после отъезда клиентов. Все номера одинаковые и пронумерованы с 1 до К. В основе плана -- журнал заявок, в каждой из которых записано время заезда и время выезда для N заявок. Заявки поступают в случайном порядке. На начало недели все номера подготовлены к заселению. После отъезда клиента на уборку номера отводится 30 минут. Уборка начинается в следующую минуту после освобождения номера. Клиент может заезжать в подготовленный номер в следующую минуту после окончания уборки. Если подготовленных номеров несколько, то выбирается номер с максимальным временем простоя; из номеров с одинаковым временем простоя -- последний номер. Если подготовленных номеров нет, клиент ждет первый подготовленный номер; при этом время отъезда не меняется. Если первый номер будет готов после запланированного времени отъезда, клиент не ждёт и сразу уезжает.

Определите максимальное время ожидания клиента перед заселением и последний номер, заселенный в течение этой недели.

Входные данные представлены в файле 26-117.txt следующим образом. В первой строке входных данных задается два числа: K -- количество номеров (1 ≤ K ≤ 1000) и N -- количество заявок (1 ≤ N ≤ 100000). В каждой из последующих N строк указано время заезда и время выезда в минутах, начиная с 0:00 воскресенья.

Запишите в ответе два числа: максимальное время ожидания клиента перед заселением и последний номер, заселенный в течение этой недели.

Пример входного файла:

2 5
10 30
15 40
40 65
55 80
56 100

При таких исходных данных первый клиент в минуту 10 сразу заезжает в номер 2, в 15-ю минуту второй клиент заезжает в номер 1 (без ожидания). На 30-й минуте первый клиент выезжает из номера 2 и в этом номере сразу начинается уборка, которая заканчивается на 60-й минуте. Поэтому третий клиент, который хотел заселиться на 40-й минуте, будет ждать 21 минуту и заселится в номер 2 на 61-й минуте. Аналогично четвёртый клиент, который хотел заселиться на 55-й минуте, должен ждать 16 минут, потому что готовый номер 1 будет готов только на 40 + 30 + 1 = 71 минуте. Последний клиент, желающий заселиться на 56-й минуте, фактически сможет сделать это только на 65 + 30 + 1 = 96 минуте, так что он будет ждать 40 минут и заселится в номер 2. Ответ: 40 2.

(Л. Евич) В операционном зале есть N банкоматов, работающих круглосуточно. Все банкоматы пронумерованы. В течение дня M клиентов хотят воспользоваться банкоматом. Клиенты обслуживаются в порядке общей очереди. Если в один момент подошли несколько клиентов, то они становятся в очередь в порядке расположения данных в файле. Клиент, стоящий первым в очереди, подходит к первому освободившемуся банкомату (если таких несколько -- к банкомату с наименьшим номером). Обслуживание очередного клиента может начаться в ту же минуту, когда банкомат станет свободным. Известно время в минутах от начала суток, когда клиент подошёл к банкомату, и время его обслуживания.

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

Входные данные представлены в файле 26-112.txt следующим образом. В первой строке входных данных задается два числа: N -- количество банкоматов и M -- количество клиентов. В каждой из последующих M строк содержится информация по одному клиенту: время начала обслуживания клиента (в минутах с начала суток) и время обслуживания (в минутах).

Запишите в ответе два числа: наименьшее количество клиентов, которые были обслужены одним банкоматом за 24 часа, и время начала обслуживания последнего клиента этим банкоматом.

Пример входного файла:

2 5
1 8
6 12
8 4
8 14
8 9

При таких исходных данных наибольшее время ожидания (10) будет у клиента со временем обслуживания 9. Наибольшее число клиентов (3) обслужит 1-й банкомат: это клиенты со временем обслуживания 8, 4 и 14. Последний клиент начинает работу со 1-м банкоматом на 13-й минуте. Ответ: 10 13.

(Л. Евич) В тренажёрном зале N тренажёров, работающих c 10:00 до 22:00. Все тренажёры пронумерованы от 1 до N. Каждый из M посетителей зала может воспользоваться любым тренажёром. Посетитель всегда выбирает свободный тренажёр с наименьшим номером. если свободных тренажёров нет, он уходит. Если в одно и то же время пришли несколько посетителей, то они занимают тренажёры в том порядке, в котором расположены данные в файле. Для каждого посетителя известно время начала и время окончания его тренировки. Время тренировки на тренажёре другого посетителя может начаться со следующей минуты после окончания времени тренировки предыдущего посетителя.

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

Входные данные представлены в файле 26-115.txt следующим образом. В первой строке входных данных задается два числа: N - количество тренажёров и M -- количество посетителей зала. В каждой из последующих M строк содержится информация по каждому посетителю: время начала и время окончания тренировки на тренажёре (в минутах от начала суток).

Запишите в ответе два числа: количество посетителей тренажерного зала, которые могли воспользоваться тренажёрами за время работы зала и номер тренажёра, на котором проводил свою тренировку последний посетитель.

Пример входного файла:

2 5
601 690
620 642
640 645
650 670
680 700

При этих исходных данных 1-й тренажёр с самого начала занимает первый посетитель. Посетители со временем прихода 620, 650 и 680 работают один за другим на 2-м тренажёре. Посетитель со временем прихода 640 уходит, потому что в этот момент свободных тренажёров нет. Всего обслужено 4 посетителя, последний начал работу на тренажёре 2. Ответ: 4 2.

(Л. Евич) В операционном зале есть N банкоматов, работающих круглосуточно. Все банкоматы пронумерованы. В течение дня M клиентов хотят воспользоваться банкоматом. Клиенты обслуживаются в порядке общей очереди. Если в один момент подошли несколько клиентов, то они становятся в очередь в порядке расположения данных в файле. Клиент, стоящий первым в очереди, подходит к первому освободившемуся банкомату (если таких несколько -- к банкомату с наименьшим номером). Обслуживание очередного клиента может начаться в ту же минуту, когда банкомат станет свободным. Известно время в минутах от начала суток, когда клиент подошёл к банкомату, и время его обслуживания.

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

Входные данные представлены в файле 26-112.txt следующим образом. В первой строке входных данных задается два числа: N - количество банкоматов и M -- количество клиентов. В каждой из последующих M строк содержится информация по одному клиенту: время начала обслуживания клиента (в минутах с начала суток) и время обслуживания (в минутах).

Запишите в ответе два числа: наименьшее количество клиентов, которые были обслужены одним банкоматом за 24 часа, и время начала обслуживания последнего клиента этим банкоматом.

Пример входного файла:

2 5
1 8
6 12
8 4
8 14
8 9

При таких исходных данных наименьшее число клиентов (2) обслужит 2-й банкомат: это клиенты со временем обслуживания 12 и 8. Последний из них начинает работу с банкоматом на 18-й минуте. Ответ: 2 18.

(Л. Евич) В операционном зале есть N банкоматов, работающих круглосуточно. Все банкоматы пронумерованы. В течение дня M клиентов хотят воспользоваться банкоматом. Клиенты обслуживаются в порядке общей очереди. Если в один момент подошли несколько клиентов, то они становятся в очередь в порядке расположения данных в файле. Клиент, стоящий первым в очереди, подходит к первому освободившемуся банкомату (если таких несколько -- к банкомату с наименьшим номером). Обслуживание очередного клиента может начаться в ту же минуту, когда банкомат станет свободным. Известно время в минутах от начала суток, когда клиент подошёл к банкомату, и время его обслуживания.

Определите наибольшее количество клиентов, которые были обслужены одним банкоматом за 24 часа, и время начала обслуживания последнего клиента. Последним обслуженным клиентом считается тот, который подошёл к любому банкомату до окончания суток (его обслуживание могло закончиться в следующие сутки).

Входные данные представлены в файле 26-112.txt следующим образом. В первой строке входных данных задается два числа: N - количество банкоматов и M -- количество клиентов. В каждой из последующих M строк содержится информация по одному клиенту: время начала обслуживания клиента (в минутах с начала суток) и время обслуживания (в минутах).

Запишите в ответе два числа: наибольшее количество клиентов, которые были обслужены одним банкоматом за 24 часа, и время начала обслуживания последнего клиента.

Пример входного файла:

2 5
1 8
6 12
8 4
8 14
8 9

При таких исходных данных наибольшее число клиентов (3) обслужит 1-й банкомат: это клиенты со временем обслуживания 8, 4 и 14. Последний клиент начинает работу со 2-м банкоматом на 18-й минуте. Ответ: 3 18.