Банк заданий
ЕГЭ по информатике Задание №26 Обработка данных с помощью сортировки

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

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

В первой строке входного файла находится одно число: $N$ – количество занятых мест (натуральное число, не превышающее 10000). В следующих $N$ строках находятся пары чисел: ряд и место выкупленного билета (числа не превышают 100000).

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

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

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

50 12

50 15

60 157

60 160

60 22

60 25

Выходные данные: 60 23.

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

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

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

В первой строке входного файла находятся два числа: $S$ – грузоподъёмность судна (натуральное число, не превышающее 100000) и $N$ – количество контейнеров (натуральное число, не превышающее 10000). В следующих $N$ строках находятся значения масс контейнеров, требующих транспортировки (все числа натуральные, не превышающие 100), каждое в отдельной строке.

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

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

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

100 4

80

30

50

40

При таких исходных данных можно транспортировать за один раз максимум 2 контейнера. Возможные массы этих двух контейнеров 30 и 40, 30 и 50 или 40 и 50. Поэтому ответ для приведённого примера: 2 50.

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

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

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

В первой строке входного файла находятся два числа: $S$ – размер свободного места на диске (натуральное число, не превышающее 100000) и $N$ – количество пользователей (натуральное число, не превышающее 10000). В следующих $N$ строках находятся значения объёмов файлов каждого пользователя (все числа натуральные, не превышающие 100), каждое в отдельной строке.

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

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

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

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

В первой строке входного файла находятся два числа: $S$ – размер свободного места на диске (натуральное число, не превышающее 10000) и $N$ – количество пользователей (натуральное число, не превышающее 1000). В следующих $N$ строках находятся значения объёмов файлов каждого пользователя (все числа натуральные, не превышающие 100), каждое в отдельной строке.

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

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

Спутник «Фотон» проводит измерения солнечной активности, результат каждого измерения представляет собой натуральное число. Перед обработкой серии измерений из неё исключают $K$ наибольших и $K$ наименьших значений (как недостоверные). По заданной информации о значении каждого из измерений, а также количестве исключаемых значений, определите наибольшее достоверное измерение, а также целую часть среднего значения всех достоверных измерений.

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

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

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

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

10 2

34

50

43

44

23

9

39

5

38

36

При таких исходных данных ответ должен содержать 2 числа – 43 и 35. Пояснение: будут отброшены значения 5, 9, 44, 50. Тогда наибольшее оставшееся значение равно 43, а среднее значение из оставшихся равно $(23+34+36+38+39+43)/6 = 35{,}5$.

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

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

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

В первой строке входного файла находятся два числа: $S$ – размер свободного места на диске (натуральное число, не превышающее 10000) и $N$ – количество пользователей (натуральное число, не превышающее 1000). В следующих $N$ строках находятся значения объёмов файлов каждого пользователя (все числа натуральные, не превышающие 100), каждое в отдельной строке.

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

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

100 4

80

30

50

40

При таких исходных данных можно сохранить файлы максимум двух пользователей. Возможные объёмы этих двух файлов 30 и 40, 30 и 50 или 40 и 50. Наибольший объём файла из перечисленных пар – 50, поэтому ответ для приведённого примера: 2 50.

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

Сервер выполняет запросы на передачу данных, при этом сведения о каждом выполненном запросе (время регистрации, идентификатор клиента, объём переданных данных) сохраняются в журнале работы, а переданные данные - в специальном разделе памяти сервера, имеющем ограниченный объём. Каждый раз, когда остаётся недостаточно свободной памяти, сервер создаёт резервную копию всех накопленных там данных, после чего освобождает раздел и продолжает выполнение запросов. Напишите программу обработки журнала работы сервера и определите идентификатор клиентского устройства, с которого на сервер был передан наибольший объём данных, а также сумму объёмов (в Кбайт) двух наибольших резервных копий специального раздела, созданных не позднее 11:59:59.

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

Первая строка входного файла (журнала работы сервера) содержит два натуральных числа: $N$ ($N< 1 000 000$) - количество строк в журнале и $K$ ($K < 1 000 000$) - вместимость специального раздела памяти сервера в Кбайт. Каждая из следующих $N$ строк содержит информацию об одном выполненном запросе: время регистрации запроса в формате ЧЧ:ММ:СС (часы, минуты, секунды), а также два натуральных числа: $C$ ($C < 1 000 000$) - идентификатор клиентского устройства и $S$ ($S$ < $K$) - объём данных запроса в Кбайт.

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

В ответе запишите два числа: сначала идентификатор устройства, с которого был передан наибольший суммарный объём данных, а затем сумму объёмов (в Кбайт) двух наибольших резервных копий специального раздела, выполненных не позднее 11:59:59.

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

8 140000

01:01:01 101 20000

03:03:03 202 110000

05:05:05 101 90000

07:07:07 303 62000

10:10:10 101 48000

15:15:15 202 12000

21:21:21 303 120000

23:23:23 404 134000

При таких исходных данных резервное копирование специального раздела выполняется четыре раза: в 05:05:05 (в объёме 130000 Кбайт), в 07:07:07 (в объёме 90000 Кбайт), в 21:21:21 (в объёме 122000 Кбайт) и в 23:23:23 (в объёме 120000 Кбайт).

Всего на сервер передано 596 000 Кбайт данных: 158000, 122000, 182000 и 134000 Кбайт от клиентов с идентификаторами 101, 202, 303 и 404 соответственно.

Ответ для приведённого примера: 303 220000.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Файлы к заданию: https://drive.google.com/file/d/1qfiPvhPid5bk0hAgHugvlit7dAer2_6f/view?usp=drive_link

Сервер выполняет запросы на передачу данных, при этом сведения о каждом выполненном запросе (время регистрации, идентификатор клиента и объём переданных данных) сохраняются в журнале работы, а сам запрос — в специальном разделе памяти сервера, имеющем ограниченный объём. Каждый раз, когда в специальном разделе остаётся недостаточно свободной памяти, сервер создаёт резервную копию всех накопленных там данных, после чего освобождает раздел и продолжает выполнение запросов. Напишите программу для обработки журнала работы сервера и с её помощью определите идентификатор устройства, с которого на сервер был передан наибольший суммарный объем данных начиная с 12:00:00, а также разность между наибольшим и наименьшим объемом резервных копий специального раздела (в Кбайт).

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

Первая строка входного файла (журнала работы сервера) содержит два натуральных числа: $N$ ($N < 1 000 000$) — количество строк в журнале и $K$ ($K < 1 000 000$) — вместимость специального раздела памяти сервера в Кбайт. Каждая из следующих $N$ строк содержит информацию об одном выполненном запросе: время регистрации запроса в формате чч:мм:сс (часы, минуты, секунды) и два натуральных числа: $C$ ($C < 1 000 000$) — идентификатор клиентского устройства и $S$ ($S < K$) — объём данных запроса в Кбайт.

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

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

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

8 140000

01:01:01 101 20000

03:03:03 202 110000

05:05:05 101 90000

07:07:07 303 62000

10:10:10 101 48000

15:15:15 202 12000

21:21:21 303 120000

23:23:23 404 134000

При таких исходных данных резервное копирование специального раздела выполняется четыре раза: в 05:05:05 (в объеме 130 000 Кбайт), в 07:07:07 (в объеме 90 000 Кбайт), в 21:21:21 (в объеме 122 000 Кбайт) и в 23:23:23 (в объёме 120 000 Кбайт). Всего начиная с 12:00:00 на сервер передано запросов от клиентов 202, 303 и 404 на объёмы 12 000, 120 000 и 134 000 Кбайт соответственно.

Ответ для приведённого примера: 404 40000.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Файл к заданию: https://drive.google.com/file/d/1J4BNjgeLGj14d5gRqxSiVsaTbnmtO_pw/view

В период сбора урожая на винограднике работают $N$ сборщиков и $K$ приемщиков винограда. Каждый сборщик собирает только один сорт винограда: традиционный сорт A или новый сорт В. Каждый приёмщик принимает урожай только одного сорта. Всем приемщикам присвоены номера начиная с единицы. Приемщики с нечётными номерами принимают урожай винограда сорта А, с чётными - сорта В. Умная камера оценивает количество собранного винограда и определяет время начала и время окончания приемки партии урожая. Время задается в минутах от начала рабочего дня. Приемщик начинает получение следующей партии винограда от сборщика не ранее, чем через 5 минут после окончания приёмки предыдущей партии. Несколько сборщиков не могут сдавать урожай одному приемщику в одно и то же время. Автоматизированная система отправляет очередного сборщика к приемщику данного сорта с минимальным номером. Если в момент прибытия партии урожая свободных приемщиков нет, то виноград передается на рынок для продажи.

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

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

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

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

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

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

2 6

30 60 А

65 1000 А

65 1000 В

1010 1300 В

65 900 А

905 1100 А

Пример приведен для двух приемщиков и шести сборщиков винограда. При таких исходных данных на рынок будет отправлена 1 партия винограда, приемщики получат 5 партий ((30 60 А), (65 900 А), (905 1100 А), (65 1000 В), (1010 1300 В)). Приемщик 1 примет 3 партии, а приёмщик 2 примет 2 партии, следовательно, наибольшее количество партий урожая примет приёмщик с номером 1.

Ответ для приведенного примера: 1 1.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Файл к заданию: https://drive.google.com/file/d/1tDGVSHICIdp0wtgvlwL1QIWlTNnQruSU/view

Сервер выполняет запросы на передачу данных, при этом сведения о каждом выполненном запросе (время регистрации, идентификатор клиента, объем переданных данных) сохраняются в журнале работы, а переданные данные - в специальном разделе памяти сервера, имеющем ограниченный объём. Каждый раз, когда остаётся недостаточно свободной памяти, сервер создает резервную копию всех накопленных там данных, после чего освобождает раздел и продолжает выполнение запросов. Напишите программу для обработки журнала работы сервера и с её помощью определите наименьший суммарный объём переданных на сервер данных среди клиентов, у которых этот объём строго больше 140 000 Кбайт, а также объем (в Кбайт) самой первой по времени резервной копии специального раздела, выполненной после 06:00:00.

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

Первая строка входного файла (журнала работы сервера) содержит два натуральных числа: $N$ ($N < 1 000 000$) - количество строк в журнале и $K$ ($K < 1 000 000$) - вместимость специального раздела памяти сервера в Кбайт. Каждая из следующих $N$ строк содержит информацию об одном выполненном запросе: время регистрации запроса в формате ЧЧ:ММ:СС (часы, минуты, секунды), а также два натуральных числа: $C$ ($C < 1 000 000$) - идентификатор клиентского устройства и $S$ ($S < K$) - объём данных запроса в Кбайт.

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

В ответе запишите два числа: сначала наименьший суммарный объем данных среди тех клиентов, чей суммарный объём строго больше 140000 Кбайт, а затем объём (в Кбайт) самой первой по времени резервной копии специального раздела, выполненной после 06:00:00.

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

8 140000

01:01:01 101 20000

03:03:03 202 110000

05:05:05 101 90000

07:07:07 303 62000

10:10:10 101 48000

15:15:15 202 12000

21:21:21 303 120000

23:23:23 404 134000

При таких исходных данных резервное копирование специального раздела выполняется четыре раза: в 05:05:05 (в объеме 130 000 Кбайт), в 07:07:07 (в объеме 90 000 Кбайт), в 21:21:21 (в объеме 122 000 Кбайт) и в 23:23:23 (в объёме 120 000 Кбайт). Всего на сервер должно быть передано 596 000 Кбайт данных: 158 000, 122 000, 182 000 и 134 000 Кбайт от клиента идентификатором 101, 202, 303 404 соответственно. Из тех клиентов чей объём строго больше 140 000 Кбайт (клиенты 101 с объёмом 158 000 Кбайт и 303 с объёмом 182 000 Кбайт), наименьший объём составляет 158 000 Кбайт. Самая первая резервная копия после 06:00:00 произошла в 07:07:07, её объём равен 90 000 Кбайт.

Ответ для приведённого примера: 158000 90000.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Файл к заданию: https://drive.google.com/file/d/1gF6tfpKpilizzeLZ-dTLJMxNoIM1ps2X/view

В крупном супермаркете установлены кассы самообслуживания. Сведения о каждой совершенной покупке (время регистрации чека, идентификатор кассы, сумма чека в рублях) автоматически сохраняются в едином электронном журнале в хронологическом порядке. Администрации магазина необходимо проанализировать пиковые нагрузки и выручку оборудования. Напишите программу для обработки журнала работы касс и с её помощью определите максимальное количество покупателей, которое было обслужено всеми кассами суммарно за любой непрерывный интервал времени длительностью ровно 15 минут (900 секунд) включительно, а также идентификатор кассы, которая принесла магазину наибольшую общую выручку за весь день.

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

Первая строка входного файла (журнала работы касс) содержит одно натуральное число: $N$ ($N < 1 000 000$) - количество записей о покупках в журнале. Каждая из следующих $N$ строк содержит информацию об одном оплаченном чеке: время регистрации в формате ЧЧ:ММ:СС (часы, минуты, секунды), а также два натуральных числа: $K$ ($K < 100$) - идентификатор кассы самообслуживания и $P$ ($P < 100 000$) - сумма чека в рублях.

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

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

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

7

12:00:00 1 1500

12:05:30 2 4200

12:12:10 1 800

12:14:59 3 3100

12:15:01 2 1200

14:30:00 1 9500

14:40:00 3 2000

При таких исходных данных, если рассмотреть интервал времени от 12:00:00 до 12:15:00 включительно, в него попадают первые 4 покупки (в 12:00:00, 12:05:30, 12:12:10 и 12:14:59). Покупка в 12:15:01 уже не входит в этот 15-минутный отрезок (так как от 12:00:00 до 12:15:01 прошло больше 15 минут). Любые другие 15-минутные интервалы содержат меньшее число покупателей. Суммарная выручка по кассам за весь день распределилась следующим образом: касса 1 выручила 11 800 рублей (1500 + 800 + 9500), касса 2 выручила 5400 рублей (4200 + 1200), касса 3 выручила 5100 рублей (3100 + 2000). Наибольшую выручку принесла касса под идентификатором 1.

Ответ для приведённого примера: 4 1.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Файл к заданию: https://drive.google.com/file/d/1Bg7ILpUoGGit9egLQ8T-bijNaHyf3bUY/view

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

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

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

Первая строка входного файла содержит одно натуральное число: $N$ ($N < 1 000 000$) — количество записей о покупках. Каждая из следующих $N$ строк содержит информацию об одном чеке: время регистрации (ЧЧ:ММ:СС), идентификатор кассы $K$ ($K < 100$), сумма чека $P$ ($P < 100 000$) и индикатор пакета $B$ (0 — пакет не взят, 1 — пакет взят).

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

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

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

5

10:00:00 1 500 1

10:05:00 2 200 0

10:10:00 1 300 0

10:12:00 3 1500 1

10:20:00 2 400 0

При таких исходных данных всего совершено 5 покупок. Пакет взяли в 2 случаях из 5, что составляет 40%. Если рассмотреть интервал времени от 10:05:00 до 10:20:00, в него попадают три покупки покупателей, не взявших пакет (в 10:05:00, 10:10:00 и 10:20:00). Это максимальное количество покупателей без пакетов в 15-минутном окне.

Ответ для приведённого примера: 40 3.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Файл к заданию: https://drive.google.com/file/d/1kyZJsL7pFKkyOVUsCgds3TSOO8CJIY81/view

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

Биологов интересуют моменты опасного сближения. Пара из одного хищника и одной жертвы считается опасной, если они зафиксированы с разницей во времени менее $T$ минут, а расстояние между их датчиками не превышает $M$ километров. Каждое зафиксированное существо может войти не более чем в одну опасную пару.

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

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

Первая строка входного файла содержит три числа: $N$ – общее количество записей в журнале, $M$ – максимальное опасное расстояние в километрах, и $T$ – максимальная разница во времени в минутах. Каждая из следующих $N$ строк содержит три целых числа: время фиксации в минутах (от 0 до 1439), координату $X$ в километрах и тип существа (1 или 2).

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

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

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

5 3 5

0 1 1

3 4 2

6 3 2

10 8 1

12 10 2

При таких исходных данных всего можно сформировать 2 опасные пары. Максимальное расстояние между датчиками среди них составляет 3 км (в паре хищника на координате 1 в минуту 0 и жертвы на координате 4 в минуту 3).

Ответ для приведённого примера: 2 3.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Файл к заданию: https://drive.google.com/file/d/1dIi1u1hgf1XBu_59pTgjGssBV963xLDI/view

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

Биологов интересуют моменты опасного сближения. Пара из одного хищника и одной жертвы считается опасной, если они зафиксированы с разницей во времени менее $T$ минут, а расстояние между их датчиками не превышает $M$ километров. Каждое зафиксированное существо может войти не более чем в одну опасную пару.

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

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

Первая строка входного файла содержит три числа: $N$ – общее количество записей в журнале, $M$ – максимальное опасное расстояние в километрах, и $T$ – максимальная разница во времени в минутах. Каждая из следующих $N$ строк содержит три целых числа: время фиксации в минутах (от 0 до 1439), координату $X$ в километрах и тип существа (1 или 2).

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

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

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

5 3 5

0 1 1

3 4 2

6 3 2

10 8 1

12 10 2

При таких исходных данных всего можно сформировать 2 опасные пары. При выборе пар (0, 1, тип 1) + (3, 4, тип 2) разница во времени равна 3 минуты, а для пары (10, 8, тип 1) + (12, 10, тип 2) разница во времени равна 2 минуты. Минимальная разница во времени среди сформированных пар составляет 2 минуты.

Ответ для приведённого примера: 2 2.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Файл к заданию: https://drive.google.com/file/d/1bW6oAq2ZSzrdEwtzZpBsLi3SDFu7j6-B/view

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

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

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

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

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

Первая строка входного файла содержит три числа: $N$ - общее количество пассажиров, прибывших на остановку, $M$ - количество автобусов за сутки, и $C$ - максимальная вместимость одного автобуса. Каждая из следующих $N$ строк содержит одно целое число - время прибытия пассажира на остановку в минутах от начала суток (от 0 до 1439). Записи упорядочены по времени прибытия. Если несколько пассажиров прибыли в одну и ту же минуту, они записываются в произвольном порядке, но занимают очередь согласно их порядку во входном файле. Далее следуют $M$ строк, каждая из которых содержит два целых числа: время прибытия автобуса в минутах от начала суток (от 0 до 1439) и количество пассажиров $P$ ($0 \le P \le C$), уже находящихся в нём. Записи об автобусах упорядочены по времени прибытия. Считается, что пассажиры, прибывшие на остановку в ту же минуту, что и автобус, успевают встать в очередь до начала посадки.

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

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

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

6 2 20

10

12

15

20

25

30

15 19

35 19

При таких исходных данных на такси уйдёт 1 пассажир (прибывший в минуту 15, так как он не поместился в автобусы в минуты 15 и 35), а максимальное время ожидания среди уехавших на автобусе составит 23 минуты (у пассажира, прибывшего в минуту 12 и уехавшего в минуту 35).

Ответ для приведённого примера: 1 23.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Файл к заданию: https://drive.google.com/file/d/1wo6x_ZdtPO_vI-KiFD3JDp8c0lIrCRrc/view

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

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

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

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

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

Первая строка входного файла содержит три числа: $N$ - общее количество пассажиров, прибывших на остановку, $M$ - количество автобусов за сутки, и $C$ - максимальная вместимость одного автобуса. Каждая из следующих $N$ строк содержит одно целое число - время прибытия пассажира на остановку в минутах от начала суток (от 0 до 1439). Записи упорядочены по времени прибытия. Если несколько пассажиров прибыли в одну и ту же минуту, они записываются в произвольном порядке, но занимают очередь согласно их порядку во входном файле. Далее следуют $M$ строк, каждая из которых содержит два целых числа: время прибытия автобуса в минутах от начала суток (от 0 до 1439) и количество пассажиров $P$ ($0 \le P \le C$), уже находящихся в нём. Записи об автобусах упорядочены по времени прибытия. Считается, что пассажиры, прибывшие на остановку в ту же минуту, что и автобус, успевают встать в очередь до начала посадки.

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

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

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

6 2 20

10

12

15

20

25

30

15 19

35 19

При таких исходных данных максимальная длина очереди перед прибытием автобуса составит 6 человек (в минуту 35 перед посадкой), а пассажир, уехавший на такси (прибывший в минуту 15), провёл на остановке 20 минут (от минуты 15 до минуты 35).

Ответ для приведённого примера: 6 20.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Файл к заданию: https://drive.google.com/file/d/1KzHmg0sVObI8nmDbjHVp4s5eW7VxpEAJ/view

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

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

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

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

Первая строка входного файла содержит целое число $N$ ($N \le 2000$) - количество заявок на монтаж кабеля. Следующие $N$ строк содержат пары чисел, обозначающих начало участка (в метрах от начала тоннеля) и его протяжённость. Каждое из чисел натуральное, не превосходящее 10000. Гарантируется, что конец участка не выходит за пределы тоннеля.

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

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

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

5

1 1000

1001 1000

2001 2500

4501 500

4501 1500

При таких исходных данных будет выполнено не более 4 заявок. Могут быть выполнены заявки с номерами 1, 2, 3 и 4 или заявки с номерами 1, 2, 3 и 5.

Ответ: 4 3999.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Файл к заданию: https://drive.google.com/file/d/1Jmd17GT-hT-Bl7zvvczhp0KGggyeIXjI/view

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

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

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

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

Первая строка входного файла содержит целое число $N$ ($N \le 2000$) - количество заявок на монтаж кабеля. Следующие $N$ строк содержат пары чисел, обозначающих начало участка (в метрах от начала тоннеля) и его протяжённость. Каждое из чисел натуральное, не превосходящее 10000. Гарантируется, что конец участка не выходит за пределы тоннеля.

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

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

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

5

1 1000

1001 500

1001 1200

2201 1000

3201 800

При таких исходных данных может быть выполнено не более 4 заявок. Для получения максимальной суммарной длины необходимо выбрать заявки 1 (1000 м), 3 (1200 м), 4 (1000 м) и 5 (800 м), что в сумме дает 4000 метров.

Ответ: 4 4000.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Файл к заданию: https://drive.google.com/file/d/1ApdzS5NavTCHRFeP08KlmqS9k7J7Txs6/view

В сувенирной мастерской есть $N$ заготовок для деревянных матрёшек. Для каждой заготовки известны два параметра: её высота и ширина. Специализация мастерской – многопредметные наборы, в которых высота и ширина каждой внутренней матрёшки строго меньше высоты и ширины внешней матрёшки. Одну матрёшку можно вложить в другую, если её высота хотя бы на 6 единиц меньше высоты внешней матрёшки, а ширина хотя бы на 4 единицы меньше ширины внешней матрёшки.

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

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

В первой строке входного файла находится число $N$ – количество заготовок для матрёшек в мастерской (натуральное число, не превышающее 10000). В следующих $N$ строках находятся пары чисел — значения высоты и ширины заготовок (все числа натуральные, не превышающие 10000), записанные через пробел, каждое значение пары - в отдельной строке.

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

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

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

5

43 20

40 18

32 15

40 12

30 10

Пример входного файла приведён для пяти заготовок и случая, когда минимальная допустимая разница между высотами составляет 3 единицы, а между ширинами — 2 единицы.

При таких исходных данных условию задачи удовлетворяют наборы матрёшек с параметрами (высота, ширина) (30, 10), (40, 18) и (43, 20) или (32, 15), (40, 18) и (43, 20) соответственно, количество матрёшек равно 3, а максимально возможная высота самой маленькой матрёшки равна 32.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Файл к заданию: https://drive.google.com/file/d/19YrrSJffJgSw_wySpJe8wSJTHeXIyvWJ/view

В сувенирной мастерской есть $N$ заготовок для деревянных матрёшек. Для каждой заготовки известны два параметра: её высота и ширина. Специализация мастерской – многопредметные наборы, в которых высота и ширина каждой внутренней матрёшки строго меньше высоты и ширины внешней матрёшки. Одну матрёшку можно вложить в другую, если её высота хотя бы на 8 единиц меньше высоты внешней матрёшки, а ширина хотя бы на 3 единицы меньше ширины внешней матрёшки.

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

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

В первой строке входного файла находится число $N$ – количество заготовок для матрёшек в мастерской (натуральное число, не превышающее 10000). В следующих $N$ строках находятся пары чисел — значения высоты и ширины заготовок (все числа натуральные, не превышающие 10000), записанные через пробел, каждое значение пары - в отдельной строке.

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

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

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

5

43 20

40 18

32 15

40 12

30 10

Пример входного файла приведён для пяти заготовок и случая, когда минимальная допустимая разница между высотами составляет 3 единицы, а между ширинами — 2 единицы.

При таких исходных данных условию задачи удовлетворяют наборы матрёшек с параметрами (высота, ширина) (30, 10), (40, 18) и (43, 20) или (32, 15), (40, 18) и (43, 20) соответственно, количество матрёшек равно 3, а максимально возможная высота самой маленькой матрёшки равна 32.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Файл к заданию: https://drive.google.com/file/d/123sRocAutT5kyX0-S_gOO-_YDM9SX1ya/view

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

Каждая карта представляется в виде строки из двух символов, где первый символ означает ранг ("6", "7", "8", "9", "T", "J", "Q", "K", "A") карты, а второй символ означает масть ("S", "C", "D", "H"). Ранги перечислены в порядке возрастания старшинства (от 6 до "A", где "T" = 10, "J" = Валет, "Q" = Дама, "K" = Король, "A" = Туз). Карты в файле записываются слитно, без пробела между рангом и мастью.

Игроку на руках сдано $K$ карт, а соперник пошел $M$ картами. Чтобы успешно отбиться в партии, игроку необходимо под каждую карту атаки подобрать отдельную подходящую карту со своих рук по следующим правилам:

– Карта атаки покрывается либо более старшей картой той же масти, либо любой козырной картой (если карта атаки была не козырной).

– Если карта атаки сама является козырной, её можно отбить только более старшей козырной картой.

– Каждую карту с рук игрока можно использовать для защиты не более одного раза.

Определите наибольшее количество партий, в которых защищающийся игрок сможет успешно отбиться, а также минимально возможный суммарный числовой эквивалент рангов всех карт, оставшихся на руках у игрока после успешного отбоя, среди всех выигранных им партий (ранги учитываются как числа: 6..9 = 6..9, "T" = 10, "J" = 11, "Q" = 12, "K" = 13, "A" = 14; если для победы в партии есть несколько способов отбиться, игрок всегда выбирает способ, минимизирующий сумму рангов оставшихся у него карт).

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

В первой строке входного файла находится число $N$ — общее количество проводимых партий (натуральное число, не превышающее 10000). Далее следуют описания $N$ партий.

Описание каждой партии состоит из трёх строк:

– Первая строка содержит два целых числа и один символ: $K$ (количество карт на руках, $K \le 35$), $M$ (количество карт атаки, $M \le 10$) и $R$ (символ козырной масти этой партии: "S", "C", "D" или "H").

– Вторая строка содержит $K$ карт, записанных через пробел — карты на руках у игрока.

– Третья строка содержит $M$ карт, записанных через пробел — карты атаки соперника.

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

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

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

2

4 2 S

8S TS 7C AH

8S 9C

3 2 H

6H 7H 8S

TH AH

При таких исходных данных в первой партии игрок имеет карты 8S, TS, 7C, AH, козырь — S. Нужно отбить карты 8S и 9C. Карта 9C отбивается козырем 8S, а карта 8S — более старшим козырем TS. Отбой успешен. На руках остаются 7C и AH, сумма их числовых рангов равна 7 + 14 = 21. Во второй партии у игрока нет карт, способных отбить TH и AH. Количество успешных партий — 1, минимальная сумма оставшихся рангов — 21.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Файл к заданию: https://drive.google.com/file/d/1iN3PADDx_-IRBzt1IiJ9DLm33LpF9ke8/view

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

Каждая карта представляется в виде строки из двух символов, где первый символ означает ранг ("6", "7", "8", "9", "T", "J", "Q", "K", "A") карты, а второй символ означает масть ("S", "C", "D", "H"). Ранги перечислены в порядке возрастания старшинства (от 6 до "A", где "T" = 10, "J" = Валет, "Q" = Дама, "K" = Король, "A" = Туз). Карты в файле записываются слитно, без пробела между рангом и мастью.

Игроку на руках сдано $K$ карт, а соперник пошел $M$ картами. Чтобы успешно отбиться в партии, игроку необходимо под каждую карту атаки подобрать отдельную подходящую карту со своих рук по следующим правилам:

– Карта атаки покрывается либо более старшей картой той же масти, либо любой козырной картой (если карта атаки была не козырной).

– Если карта атаки сама является козырной, её можно отбить только более старшей козырной картой.

– Каждую карту с рук игрока можно использовать для защиты не более одного раза.

Определите наименьшее количество козырных карт, которое суммарно потратит игрок на отбой во всех успешно выигранных им партиях, а также максимально возможный суммарный числовой эквивалент рангов всех карт, использованных для защиты, в той из успешных партий, где на отбой потребовалось наибольшее количество козырных карт (ранги учитываются как числа: 6..9 = 6..9, "T" = 10, "J" = 11, "Q" = 12, "K" = 13, "A" = 14; если в партии существует несколько способов отбиться с минимальным расходом козырей, игрок выбирает тот способ, который максимизирует сумму рангов карт, сыгравших в защите).

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

В первой строке входного файла находится число $N$ — общее количество проводимых партий (натуральное число, не превышающее 20000). Далее следуют описания $N$ партий.

Описание каждой партии состоит из трёх строк:

– Первая строка содержит два целых числа и один символ: $K$ (количество карт на руках, $K \le 35$), $M$ (количество карт атаки, $M \le 10$) и $R$ (символ козырной масти этой партии: "S", "C", "D" или "H").

– Вторая строка содержит $K$ карт, записанных через пробел — карты на руках у игрока.

– Третья строка содержит $M$ карт, записанных через пробел — карты атаки соперника.

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

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

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

2

4 2 S

8S TS 7C AH

8S 9C

3 2 H

6H 7H 8S

TH AH

При таких исходных данных в первой партии игрок имеет карты 8S, TS, 7C, AH, козырь — S. Нужно отбить карты 8S и 9C. Чтобы отбить 9C с минимальным расходом козырей, игрок мог бы взять любой козырь, но не козырных карт масти 'C' старше 9 нет. Карта 8S отбивается более старшим козырем TS, а 9C отбивается козырем 8S. Отбой успешен. Из двух карт защиты обе являются козырями (потрачено 2 козыря). Сумма рангов защитных карт равна 8 + 10 = 18. Во второй партии у игрока нет карт, способных отбить TH и AH, партия проиграна. Всего успешных партий одна, минимальное сумма козырей — 2, и наибольшая сумма рангов защитных карт среди партий с максимальным числом козырей — 18.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Файл к заданию: https://drive.google.com/file/d/1hlfdYtBRFI0QjNx0dFDIbCU320J7EI7i/view