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

(И. Карпачев) На улице стоят 5-этажные дома, в каждом из которых 9 подъездов, и на одном этаже каждого подъезда по 8 квартир. Курьерской доставке известны номера домов и квартир, в которые необходимо доставить заказ. Требуется определить наименьший номер дома, в который поступило хотя бы 2 заказа в квартиры, расположенные на одном этаже и в одном подъезде. Для найденного дома определите наибольший номер квартиры, в которую нужно доставить заказ.

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

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

8
101 5
101 16
102 17
102 18
102 124
103 86
103 144
103 145

При таких исходных данных на одном этаже находятся квартиры 17 и 18 в доме 102. Наибольший номер квартиры в этом доме, куда нужно доставить заказ -- 124. Ответ: 102 124.

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

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

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

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

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

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

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

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

6
40 70
10 40
85 30
60 30
35 35
40 50

При таких исходных данных ответом 1-й курьер выполнит заказ 10--50. Для доставки партии в течение интервала 35--70 потребуется 2-й курьер, а для партий с интервалами 40--90 и 40--110 потребуются ещё два курьера. Партию в интервале 60--90 сможет обработать уже освободившийся 1-й курьер, и партию в интервале 85--115 -- второй. Ответ: 4 2.

(И. Карпачев) У прокрастинатора накопилось невероятно много заказов. Известно, что на выполнение одного заказа уходит ровно один день. Для каждого заказа известна стоимость и количество дней, оставшихся до сдачи заказа. Прокрастинатор понял, что выполнить все заказы он не сможет. Поэтому он решил выполнить часть заказов так, чтобы при этом получить максимальный доход. Так же ему интересно, какова при этом будет минимальная цена одного заказа.

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

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

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

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

5
2 10
1 20
2 25
2 70
3 24

При таких исходных данных прокрастинатор сможет получить сумму 119, выполнив сначала заказ 4 стоимостью 70, затем заказ 3 стоимостью 25 и в конце заказ 5 стоимостью 24. Ответ: 119 24.

(Н. Кургуз) В поезде, состоящем из M вагонов (вагоны пронумерованы от 1 до M), размещаются N групп людей, в каждой из которых не более 4 человек, среди них могут быть дети. Каждый вагон содержит K четырёхместных купе, а также K двухместных боковых блоков. Каждая группа, в которой больше двух человек, размещается в отдельном купе, а каждая группа из 1 или 2 человек -- в отдельном боковом блоке или купе. Разделять группы нельзя. В первую очередь размещаются группы с большей численностью, а при равной численности приоритет получают те, в которых больше детей. Группы размещаются на первом подходящем месте в вагоне с наименьшим номером. Определите наибольшее количество детей, которых удастся разместить в поезде, а также номер вагона, в котором останется наибольшее количество свободных мест. Если таких вагонов несколько, укажите наименьший номер подходящего вагона.

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

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

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

12
2 2
3 1
3 0
1 0
2 0
4 2
3 2
2 0
4 1
3 1
2 1
3 2
1 0

При таких исходных данных смогут заселиться группы (4,2), (4,1), (3,2), (3,2), (2,1), (2,0), (2,0), (1,0), в 1 вагоне свободных мест -- 0, во втором -- 3. Ответ: 8 2.

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

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

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

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

5 2
10 5 0
11 3 1
12 4 0
13 4 1
14 5 0

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

На автозаправке работают две заправочные колонки. Заправиться дизельным топливом можно только в колонке 1, бензином А-76 -- только в колонке 2. Клиент заезжает на заправку и встаёт в очередь к той колонке, в которой есть необходимое ему топливо. Если нужное топливо есть в обеих колонках, клиент выбирает ту, очередь к которой в данный момент меньше. Если обе очереди одинаковые, клиент выбирает колонку с меньшим номером. Если при этом в очереди к выбранной колонке уже стоит 5 или более машин (считая ту машину, которая сейчас заправляется), клиент сразу уезжает.

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

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

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

5
10 5 0
11 3 1
12 4 0
13 4 1
14 5 0

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

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

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

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

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

5
10 150
100 110
131 170
131 180
120 130

При таких исходных данных можно провести максимум два мероприятия, например, по заявкам 2 и 3. Последнее мероприятие может начаться не позднее, чем в момент времени 131, так что максимальный перерыв составит 131 -- 110 = 21 минуту. Ответ: 2 21.

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

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

Запишите в ответе два числа: -- максимальное количество уроков, которые сможет посетить Петя, и время селфи.

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

4
3 8
1 6
6 9
5 20

При таких исходных данных Петя может посетить максимум два урока: \[1, 6), \[6, 9); время селфи -- 6. Ответ: 2 6.

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

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

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

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

4
100 200
200 250
400 500
420 480

При таких исходных данных хотя бы один фильм показывался в промежутки времени \[100; 250) и \[400; 500). Суммарное время равно (250-100) + (500-400) = 250. Максимальный непрерывный отрезок времени, в течение которого показывался хотя бы один фильм равен 250-100 = 150. Ответ: 250 150.

(Л. Шастин) Проспект длиной K метров освещён N фонарями, стоящими вдоль него. Администрация города выяснила, что количество включённых фонарей избыточно для освещения всего проспекта -- какие-то из них можно выключить, чтобы сэкономить электроэнергию, при этом проспект все равно останется освещён полностью. Входной файл содержит данные о метках начала и конца отрезков, освещаемых фонарями. Определите, какое максимальное количество фонарей можно выключить так, чтобы проспект остался освещён полностью, а также общее количество фонарей, которые, если их включить, освещают K-й метр проспекта.

Примечание: начало проспекта определено 1-м метром, конец -- K-м метром.

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

Запишите в ответе два числа: максимальное количество фонарей, которые можно выключить, и количество фонарей, которые, если их включить, освещают K-й метр проспекта.

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

5 50
1 30
28 50
20 40
1 10
15 50

При таких исходных данных можно выключить 3 фонаря: второй, третий и четвёртый. K-й метр освещается двумя фонарями (если они включены): фонарь {28, 50} и фонарь {15, 50}. Ответ: 3 2.

(Л. Шастин) В отеле есть K жилых номеров, предназначенных для размещения туристов. Все номера пронумерованы, начиная с единицы. Известно время, в которое каждая группа туристов заселяются в номера; время, в которое они планируют их освободить, а также количество номеров, которое потребуется для того, чтобы разместить всю группу туристов сразу. Каждая группа туристов заселяется в свободные номера с наименьшими номерами. Если несколько групп туристов пришли одновременно, то прежде всего обслуживаются группы, которые планируют уйти раньше и для размещения которых требуется меньшее количество номеров. На заселение и выселение туристов уходит одна минута. Со следующей минуты можно заселять в освободившийся номер других туристов. Если группа туристов пришла, но необходимого количества (которого достаточно для заселения их всех) свободных номеров нет -- вся группа уходит, потому что заселиться не может.

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

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

-- минута заселения группы туристов;

-- минута, до которой группа туристов планирует проживать в номерах;

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

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

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

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

10
5
30 60 5
40 1110 2
30 60 3
60 120 1
120 1440 2

При таких исходных данных первая, вторая, третья и пятая группа туристов смогут заселиться в номера. В первые 29 минут от начала дня все номера были свободны, далее до 40 минуты были свободны 2 номера. С 40-й и до 60-й минуты все номера были заняты на протяжении 21-й минуты, а затем до конца дня хотя бы один из номеров всегда был свободен. Значит, суммарное время, в которое хотя бы один из номеров был свободен, равно 1440 - (60 - 40 + 1) = 1440 - 21 = 1419. Ответ: 4 1419.

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

Входные данные представлены в файле 26-136.txt следующим образом. В первой строке входного файла находится два натуральных числа, не превышающих 10000: N -- количество товаров и M -- средний чек. В следующих N строках записано по два числа: цена товара (она же вид товара) и статус товара (0 -- не продан; 1 -- продан).

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

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

5 60
43 1
90 1
43 0
43 1
90 0

Для данного примера цена самого популярного дорогого товара -- 90 (продан 1 раз), а самого популярного из дешёвых -- 43 (продан дважды). Их сумма = 90 + 43·2 = 176. Продано товаров = 3, всего их в наличии было 5. Осталось = 5 - 3 = 2. Ответ: 176 2.

(Л. Шастин) Во дворце спорта идёт активная продажа билетов на предстоящий баскетбольный матч. Имеется информация об уже распределенных между болельщиками местах. При этом точно известно, что первое и последнее место в каждом из рядов занято. Хорошим называется такое место, что слева и справа от него есть ровно по 5 свободных мест. Найдите ряд с наибольшим номером, в котором есть хотя бы одно хорошее место, а также общее количество хороших мест во всех рядах.

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

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

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

11
5 1
20 30
5 7
20 18
5 30
20 1
20 4
20 16
5 13
20 10
20 24

Для данного примера подходит ряд 5, в котором слева и справа от 7 места есть ровно по 5 свободных мест, и ряд 20, в котором подходят 10-е и 24-е места. В ответ пойдёт ряд с наибольшим номером, содержащий хорошие места, и общее количество хороших мест. Ответ: 20 3.

(Г. Шапошников) Начальник ведет прием граждан. При этом, при формировании очередности приема приняты следующие правила: 1) пенсионеры пользуются преимуществом перед всеми остальными гражданами; 2) женщины пользуются преимуществом перед мужчинами; 3) посетители одной категории принимаются в порядке «живой» очереди. Каждый приём длится определенное время (мин.).

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

Входные данные представлены в файле 26-134.txt следующим образом. Первая строка входного файла содержит два натуральных числа N и T (1 ≤ N ≤ 1000, 1 ≤ T ≤ 10000) -- количество принятых людей и интересующий нас момент времени, соответственно. Каждая из следующих N строк содержит три значения: время, когда посетитель пришел на прием; длительность приема; категория посетителя, одна из трех букв: W (женщина), M (мужчина) и G (пенсионер).

Запишите в ответе два числа: количество посетителей, принятых к моменту времени T (считая посетителя, находящегося на приёме в этот момент), и количество принятых посетителей той же категории, что и человек, находящийся на приеме в момент времени T.

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

5 12
1 6 W
4 7 M
5 3 G
8 9 M
11 5 G

При таких исходных данных с 1-й по 7-ю минуту на приёме будет находиться женщина, пришедшая в 1-ю минуту. С 7-й по 10-ю минуту пенсионер, пришедший в 5-ю минуту. С 10-й по 17-ю -- мужчина, пришедший в 4-ю минуту. Всего будет принято 3 человека, из них один мужчина, находящийся на приёме в момент 12. Ответ: 3 1.

(А. Богданов) Проводится вычислительный эксперимент для определения необходимого количества самокатов на разных парковках города в начальный момент времени. Всего есть 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 1.

(А. Рогов) В отделении банка используется система распознавания лиц, с помощью которой фиксируется время, когда посетитель пришел в отделение и время, когда он вышел. Для удобства время хранится как целое число, показывающее, сколько секунд прошло от начала суток до события. Посетителей банка обслуживают операторы, которые пронумерованы, начиная с 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.