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

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

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

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

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

5
10 90 1
100 130 2
120 135 5
130 170 3
140 180 4

Для приведённого примера наибольшее время 153 = (90-10+1) + (130-100+1) + (180-140+1) конференц-зал будет занят при проведении первого и второго по счёту мероприятий в списке. Общая выручка за аренду составит 1 + 2 + 4 = 7. Ответ: 153 7.

*(А. Кабанов) В магазине для упаковки подарков есть N кубических коробок красного, зелёного и синего цвета. Самой интересной считается упаковка подарка по принципу матрёшки: подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и т. д., при этом цвета коробок отличаются. Одну коробку можно поместить в другую, если длина её стороны хотя бы на K единиц меньше длины стороны другой коробки. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки, где будет находиться подарок. Размер подарка позволяет поместить его в самую маленькую коробку.

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

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

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

8 7
50 R
48 G
43 B
40 R
36 B
34 G
22 B
17 R

Пример входного файла приведён для случая трёх коробок красного цвета, двух коробок зелёного цвета и трёх коробок синего цвета. При таких исходных данных условию задачи удовлетворяет набор коробок 50, 43, 34, 22, то есть количество коробок равно 4, а длина стороны самой маленькой коробки 22. Ответ: 4 22.

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

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

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

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

5
129
120
96
120
90

При таких исходных данных условию задачи удовлетворяют наборы коробок с длинами сторон 90, 120 и 129 или 96, 120 и 129 соответственно. В обоих случаях количество коробок равно 3, а максимальная длина стороны самой маленькой коробки равна 96. Ответ: 3 96.

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

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

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

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

5
10 90 1
100 130 2
120 135 5
130 170 3
140 180 4

Для приведённого примера наибольшая выручка (10) может быть получена при проведении первого, третьего и последнего мероприятий в списке. Общая длительность этих мероприятий равна (90-10+1) + (135-120+1) + (180-140+1) = 138. Ответ: 10 138.

(ЕГКР-2024) В банке дистанционной проверяющей системы имеется более 100000 заданий. Все задачи пронумерованы, начиная с единицы. Эти задания в течение учебного периода решают участники различных курсом. Каждому студенту при регистрации присваивается уникальный идентификатор -- натуральное число, не превышающее 1000000. Студент может сдать несколько различных правильных решений одной задачи, при этом в зачёт идёт только одно из них.

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

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

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

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

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

9
40 3
60 33
60 33
50 125
50 126
50 127
40 4
50 72
50 126

Для приведённого примера студент с идентификационным номером 50 решил наибольшее количество задач с идущими подряд номерами (3 задачи с номерами 125, 126 и 127). Ответ: 50 3.

Участники викторины отвечают на 10 вопросов, сложность которых оценивается числом от 10 до 100. При удачном ответе на вопрос стоимостью Q участник получает Q баллов, при неправильном ответе на такой вопрос он получает Q штрафных баллов, которые вычитаются из результата. Участник может не отвечать на какие-то вопросы, при этом его сумма баллов не изменяется. Чтобы определить победителей, для каждого участника вычисляются три показателя:

1)    сумма – сумма набранных баллов;
2)    штрафы – сумма штрафных баллов за неправильные ответы;
3)    пропуски – количество вопросов, на которые участник вообще не отвечал.

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

Входные данные представлены в файле 26-156.txt следующим образом. В первой строке входного файла записано натуральное число N, не превышающее 10 000 --- количество участников викторины. Вторая строка содержит 10 чисел, разделённых пробелом: «стоимости вопросов». В каждой из следующих N строках через пробел записаны через пробел 11 чисел: сначала код участника, а затем 10 чисел, характеризующих ответы этого участника на вопросы (1, если ответ верный; -1, если ответ неверный и 0, если участник не отвечал на вопрос).

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

Участники викторины отвечают на 10 вопросов, сложность которых оценивается числом от 10 до 100. При удачном ответе на вопрос стоимостью Q участник получает Q баллов, при неправильном ответе на такой вопрос он получает Q штрафных баллов, которые вычитаются из результата. Участник может не отвечать на какие-то вопросы, при этом его сумма баллов не изменяется. Чтобы определить победителей, для каждого участника вычисляются три показателя:
1)    сумма – сумма набранных баллов;
2)    штрафы – сумма штрафных баллов за неправильные ответы;
3)    пропуски – количество вопросов, на которые участник вообще не отвечал.

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

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

Входные данные представлены в файле 26-156.txt следующим образом. В первой строке входного файла записано натуральное число N, не превышающее 10 000 --- количество участников викторины. Вторая строка содержит 10 чисел, разделённых пробелом: «стоимости вопросов». В каждой из следующих N строках через пробел записаны через пробел 11 чисел: сначала код участника, а затем 10 чисел, характеризующих ответы этого участника на вопросы (1, если ответ верный; -1, если ответ неверный и 0, если участник не отвечал на вопрос).

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

Участники викторины отвечают на 10 вопросов, сложность которых оценивается числом от 10 до 100. При удачном ответе на вопрос стоимостью Q участник получает Q баллов, при неправильном ответе на такой вопрос он получает Q штрафных баллов, которые вычитаются из результата. Участник может не отвечать на какие-то вопросы, при этом его сумма баллов не изменяется. Чтобы определить победителей, для каждого участника вычисляются три показателя:

1)    сумма – сумма набранных баллов;
2)    штрафы – сумма штрафных баллов за неправильные ответы;
3)    пропуски – количество вопросов, на которые участник вообще не отвечал.

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

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

Входные данные представлены в файле 26-156.txt следующим образом. В первой строке входного файла записано натуральное число N, не превышающее 10 000 --- количество участников викторины. Вторая строка содержит 10 чисел, разделённых пробелом: «стоимости вопросов». В каждой из следующих N строках через пробел записаны через пробел 11 чисел: сначала код участника, а затем 10 чисел, характеризующих ответы этого участника на вопросы (1, если ответ верный; -1, если ответ неверный и 0, если участник не отвечал на вопрос).

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

(В. Ланская, Р. Ягафаров) В некотором городе существует база данных о зарегистрированных автомобильных нарушениях за последние полгода. Марка каждого автомобиля закодирована как целое число, каждый автомобиль отнесен к одному из трёх классов: эконом, средний, премиум. Возможно, что автомобили одной марки имеют разные классы, это указывает на различные варианты комплектации. В таком случае каждую комбинацию «марка -- класс» следует рассматривать как отдельную марку. На основе этой статистики необходимо определить водители какой марки автомобилей в сумме заплатили больше всего за все нарушения. Если таких марок несколько, то выбирается марка с наибольшим номером, и если и таких марок несколько, то марка с наивысшим классом.

Входные данные представлены в файле 26-155.txt следующим образом. В первой строке входного файла записано натуральное число N, не превышающее 10 000 --- количество нарушений, которые занесены в базу. В каждой из следующих N строках через пробел записаны три числа --- код марки автомобиля (от 1000 до 9999), сумма штрафа (натуральное число, не превышающее 5000) и код класса (1 --- эконом, 2 --- средний, 3 --- премиум).

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

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

4
6666 750 1
2222 1050 2
3333 550 1
2222 1100 2

При таких исходных данных наибольшую сумму (1050 + 1100 = 2150) заплатили водители марки 2222 класса 2. Ответ: 2222 2150.

(Демо-2025) Во время сессии студенты сдают 4 экзамена, за каждый из которых можно получить отметку от 2 до 5 баллов. Студенты, получившие хотя бы одну «двойку», считаются не сдавшими сессию. Результаты сессии публикуются в виде рейтингового списка, в котором сначала указаны идентификационные номера студентов (ID), сдавших сессию, в порядке убывания среднего балла за сессию, а в случае равенства средних баллов -- в порядке возрастания ID. Затем располагаются ID студентов, не сдавших сессию: сначала -- получивших одну «двойку», затем -- две «двойки», потом ID студентов с тремя «двойками» и, наконец, ID студентов, получивших по 2 балла за каждый из экзаменов. Если студенты имеют одинаковое количество «двоек», то их ID в рейтинге располагаются в порядке возрастания. Повышенную стипендию получают студенты, занявшие в рейтинговом списке первые 25% мест, при условии отсутствия у них «двоек». Гарантируется, что без «двоек» сессию сдали не менее 25% студентов. Найдите ID студента, который занимает последнее место среди студентов с повышенной стипендией, а также ID первого в рейтинговом списке студента, который имеет более двух «двоек».

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

ID студента (целое положительное число, не превышающее 100 000) и четыре оценки, полученные им за сессию. Гарантируется, что общее число студентов N кратно 4 и хотя бы один студент имеет более двух «двоек». Во входном файле все ID различны.

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

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

8
4 4 4 4 4
7 5 5 5 2
10 3 4 4 5
1 4 4 4 3
6 3 5 5 3
2 2 2 2 2
13 2 2 2 3
3 3 3 3 3

При таких исходных данных рейтинговый список ID имеет вид: 4 6 10 1 3 7 13 2. Ответ: 6 13.

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

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

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

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

8
10 100 1
3 10 0
10 100 0
2 10 1
10 100 0
3 10 1
11 100 0
1 200 0

При таких исходных данных дорогими являются товары с ценой 100 и 200 рублей. Больше всего (2 шт.) было продано товара артикула 10, в продаже осталась одна единица такого товара стоимостью 100. Ответ: 100 10.

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

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

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

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

8
10 100 1
3 10 0
10 100 0
2 10 1
10 100 0
3 10 1
11 100 0
1 200 0

При таких исходных данных дорогими являются товары с ценой 100 и 200 рублей. Больше всего (2 шт.) было продано товара артикула 10 на сумму 200, в продаже осталась одна единица такого товара. Ответ: 200 1.

(ЕГЭ-2024) Отбор кандидатов в матросы происходит по сумме баллов трех экзаменов. На заранее известное количество мест отбираются кандидаты, набравшие большую сумму баллов по результатам трех экзаменов. Все кандидаты, набравшие определенную сумму баллов или больше, зачисляются на имеющиеся места. Такой балл называется проходным. Если после заполнения имеющихся мест кандидатами с проходным баллом остаются незаполненные места, но кандидатов, набравших следующую сумму баллов, больше чем вакантных мест, набранная этими кандидатами сумма баллов называется полупроходным баллом. Из числа кандидатов, набравших полупроходной балл, на имеющиеся места принимаются кандидаты, имеющие более высокий балл за собеседование, а при равенстве баллов за собеседование -- приоритет имеют кандидаты с наименьшими ID. Для данного множества кандидатов определите ID последнего кандидата с набранным проходным баллом, а также количество кандидатов, набравших полупроходной балл.

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

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

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

6 3
1 90 90 90 10
3 60 70 80 8
5 65 60 90 6
8 50 80 100 4
4 40 95 80 7
11 80 63 72 6

При таких входных данных проходной балл равен 230, при этом ID последнего кандидата с проходным баллом равен 8. Полупроходной балл (215) -- набрали три человека. Ответ: 8 3.

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

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

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

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

7 7 8
1 1
6 6
5 5
6 7
4 4
2 2
3 3

Условию задачи удовлетворяют места 7 и 8 в ряду 5: перед креслами 7 и 8 нет занятых мест и это последняя из двух возможных пар в этом ряду. В рядах б и 7 искомую пару найти нельзя. Ответ: 5 8.

(И. Карпачев) На улице стоят 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.