Экзамены и диагностики

(ЕГЭ-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.

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

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

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

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

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

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

Пусть максимальное время обслуживания равно 15 минутам. При таких исходных данных клиенты обслуживаются следующим образом. 1-й банкомат: клиенты со временем обслуживания 8, 4, 14; 2-й банкомат: клиент со временем обслуживания 12. Клиента со временем 9 обслужить за 15 минут не удаётся. Последний обслуженный клиент (со временем 14) начинает работу с 1-м банкоматом на 13-й минуте. Ответ: 4 1.

(Досрочный ЕГЭ-2023) Входной файл содержит заявки пассажиров, желающих сдать свой багаж в камеру хранения. В заявке указаны время сдачи багажа и время освобождения ячейки (в минутах от начала суток). Багаж одного пассажира размещается в одной свободной ячейке с минимальным номером. Ячейки пронумерованы начиная с единицы. Размещение багажа в ячейке или её освобождение происходит в течение 1 мин. Багаж можно поместить в только что освобождённую ячейку начиная со следующей минуты. Если в момент сдачи багажа свободных ячеек нет, то пассажир уходит. Определите, сколько пассажиров сможет сдать свой багаж в течение 24 ч и какой номер будет иметь ячейка, которую займут последней. Если таких ячеек несколько, укажите минимальный номер ячейки.

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

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

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

2
5
30 60
40 1000
59 60
61 1000
1010 1440

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

В ходе эксперимента заряженные частицы попадают на чувствительный экран размером 100 000 × 100 000 точек. При попадании каждой частицы на экран в протоколе фиксируются координаты попадания: номер ряда (целое число от 1 до 100 000) и номер позиции в ряду (целое число от 1 до 100 000). Точка экрана, в которую попала хотя бы одна частица, считается светлой, точка, в которую ни одна частица не попала, -- тёмной. Линией называют группу точек, расположенных в одном ряду подряд. Линия должна начинаться и заканчиваться светлыми точками, между которыми могут располагаться как светлые, так и тёмные точки, но тёмных точек может быть не более 10 подряд. По заданному протоколу нужно определить наибольшую длину одной линии и номер ряда, в котором это находится эта линия. Если таких рядов несколько, выберите максимальный номер подходящего ряда.

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

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

6
2 12
1 4
2 30
2 10
4 15
2 5

При этих данных линия максимальной длины находится в ряду 2, она включает светлые точки с позициями 5, 10 и 12, а также все тёмные точки между ними. Общая длина линии равна 8. Ответ: 8 2.

(PRO100 ЕГЭ) В супермаркете проводится акция «каждый шестой товар в чеке за полцены». У покупателя есть 100 000 рублей. Какое максимальное количество товаров может купить покупатель, если он сам выберет расположение товаров в чеке?

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

Входные данные представлены в файле 26-109.txt следующим образом. В первой строке записано число N -- количество товаров в магазине (натуральное число, не превышающее 10 000). В следующих N строках находятся числа, обозначающие цены товаров в рублях (все числа чётные натуральные, не превышающие 10 000), каждое -- в отдельной строке. Цены товаров указаны в произвольном порядке.

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

5
4
80
30
50
40

Пусть и покупателя есть 140 рублей и идёт акция «каждый второй товар в чеке за полцены». При таких исходных данных ответом на первый вопрос будет число 5 (расположение товаров в чеке: 40 50 4 80 30, сумма покупки: 40 + 50/2 + 4 + 80/2 + 30 = 139), на второй вопрос -- число 1 (140 - 139 = 1).