Банк заданий
ЕГЭ по информатике

Текстовый файл состоит из десятичных цифр и заглавных букв латинского алфавита. Определите в прилагаемом файле максимальное количество идущих подряд символов, начинающихся с подстроки $100$ и заканчивающихся буквой $B$, среди которых буква $X$ встречается не более 70 раз, а подстрока $BOSS$ содержится ровно 15 раз.

В ответе запишите число - количество символов в найденной последовательности.

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

Текстовый файл содержит только символы тире и точка ($«-»$ и $«.»$), представляющие собой запись азбуки Морзе. Буквой в данной задаче называется любая последовательность из одной, двух или трех точек, после которой обязательно следует ровно одно тире (играющее роль разделителя).

Например, комбинации $«.-»$, $«..-»$ и $«...-»$ являются корректными буквами, а комбинации $«----»$, $«....-»$ или просто $«-»$ буквами не считаются.

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

В ответе запишите число – количество букв в найденной последовательности.

Например, в строке $«-.--...-..-..»$ есть буквы $«.-»$ (1 точка и тире), $«...-»$ (3 точки и тире) и $«..-»$ (2 точки и тире). Непрерывная последовательность $«...-..-»$ дает ответ 2.

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

Текстовый файл содержит только символы тире и точка ($«-»$ и $«.»$), представляющие собой запись азбуки Морзе. Буквой в данной задаче называется любая последовательность из одной, двух или трех точек, после которой обязательно следует ровно одно тире (играющее роль разделителя).

Например, комбинации $«.-»$, $«..-»$ и $«...-»$ являются корректными буквами, а комбинации $«----»$, $«....-»$ или просто $«-»$ буквами не считаются.

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

В ответе запишите число – количество символов в найденной последовательности.

Например, в строке $«-.--...-..-..»$ есть буквы $«.-»$ (1 точка и тире), $«...-»$ (3 точки и тире) и $«..-»$ (2 точки и тире). Непрерывная последовательность $«...-..-»$ дает ответ 2.

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

В текстовом файле находится строка, состоящая из цифр от $0$ до $9$ и заглавных латинских букв $X$, $Y$, $Z$. Известно, что в строке зашифровано сообщение с помощью Полибианского квадрата. Каждая буква исходного сообщения кодируется парой цифр, где первая цифра — номер строки (от 1 до 5), а вторая цифра — номер столбца (от 1 до 5).

Зашифрованные буквы в файле могут разделяться ровно одним символом-разделителем ($X$, $Y$ или $Z$). При этом разделитель между двумя зашифрованными буквами может как присутствовать, так и отсутствовать.

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

Например, для строки $11X1534Z45YY11$ подстрока $11X1534Z45$ является корректной (состоит из гласных $11$, $15$, $34$, $45$, разделенных одиночными $X$ и $Z$, а пара $15$ и $34$ идет без разделителя, что разрешено). Ее длина — 10 символов. Идущие подряд разделители $YY$ прерывают цепочку.

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

В текстовом файле находится строка, состоящая из цифр от $0$ до $9$ и заглавных латинских букв $X$, $Y$, $Z$. Известно, что в строке зашифровано сообщение с помощью Полибианского квадрата. Каждая буква исходного сообщения кодируется парой цифр, где первая цифра — номер строки (от 1 до 5), а вторая цифра — номер столбца (от 1 до 5).

Зашифрованные буквы в файле могут разделяться ровно одним символом-разделителем ($X$, $Y$ или $Z$). При этом разделитель между двумя зашифрованными буквами может как присутствовать, так и отсутствовать.

Определите минимальную длину подстроки, содержащую не менее 60 символов-разделителей, которая может представлять собой непрерывную цепочку корректно зашифрованных согласных букв и разделяющих их одиночных символов $X$, $Y$, $Z$. Символ-разделитель не может стоять в самом начале или в самом конце искомой подстроки.

Например, для строки $11X43Y44Z33YY11$ (где $43$, $44$, $33$ — согласные, а $11$ — гласная) и условия «содержащую не менее 2 символов-разделителей» искомой подстрокой является $43Y44Z33$. В ней ровно 2 разделителя ($Y$ и $Z$), а по краям стоят зашифрованные согласные. Ее длина — 8 символов. Идущие подряд разделители $YY$ прерывают цепочку.

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

В текстовом файле находится строка из букв $X$, $Y$, $Z$. Подстроки называются неперекрывающимися, если они не имеют общих символов (индексы их символов в исходном файле не пересекаются). Каждая неперекрывающаяся подстрока должна начинаться с одной и той же выбранной буквы, иметь длину не менее 17 символов и содержать не более 4 букв $Y$. Определите максимальное количество таких подстрок в файле.

Например, для строки $XYYYYXZXYYYYXZ$ и условий «длиной не менее 3 символов, не более 2 букв $Y$» максимальное количество таких подстрок равно 2. При выборе стартовой буквы $X$: $XYY$ (символы 1–3) и $XZXYY$. При выборе стартовой буквы $Y$: $YYXZX$ и $YYXZ$, для $Z$ получится выделить только 1 подстроку: $ZXYY$.

Файл к заданию: https://drive.google.com/file/d/17LqpgpEMxUUu-14NlmS55fwZOo-rZvMh/view

В текстовом файле находится строка из букв $X$, $Y$, $Z$. Подстроки называются неперекрывающимися, если они не имеют общих символов (индексы их символов в исходном файле не пересекаются). Каждая подстрока должна начинаться с одной и той же буквы, иметь длину не менее 24 символов и содержать не более 3 букв $Z$.

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

Например, для строки $XXZXZZZXXYXZZZXX$ и условий «длина от 4 символов, не более 2 букв $Z$» максимальное количество подстрок равно 2 (для $X$ и $Z$). Для буквы $X$ суммарная длина максимальна и равна 11 (подстроки $XXZXZ$ и $XXYXZZ$).

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

Текстовый файл состоит из десятичных цифр и заглавных букв латинского алфавита. Определите в прилагаемом файле минимальное количество идущих подряд символов, среди которых пара символов $26$ (в указанном порядке) встречается ровно 18 раз, согласная буква встречается ровно один раз, искомая последовательность заканчивается этой единственной согласной буквой.

В ответе запишите число - количество символов в найденной последовательности.

Для выполнения этого задания следует написать программу.

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

Текстовый файл состоит из десятичных цифр и заглавных букв латинского алфавита. Определите в прилагаемом файле минимальное количество идущих подряд символов, среди которых пара символов $42$ (в указанном порядке) встречается ровно 15 раз, гласная буква встречается ровно один раз, искомая последовательность заканчивается этой единственной гласной буквой.

В ответе запишите число - количество символов в найденной последовательности.

Для выполнения этого задания следует написать программу.

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

Текстовый файл состоит из заглавных букв латинского алфавита - цифр римской системы счисления $I$, $V$, $X$, $L$, $C$, $D$, $M$. Найдите в файле все непрерывные последовательности символов, являющиеся корректными римскими записями чисел, которые невозможно расширить влево или вправо (то есть символы слева и справа от последовательности, при их наличии, не могут быть частью этой римской записи). Каждое найденное число последовательно обрабатывается по следующим правилам:

1. Вычисляется десятичное значение числа.

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

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

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

Примечание.

В римской системе счисления приняты следующие правила:

1) в качестве цифр используют заглавные латинские буквы $I$, $V$, $X$, $L$, $C$, $D$, $M$, числовое значение которых 1, 5, 10, 50, 100, 500 и 1000 соответственно;

2) цифры $V$, $L$, $D$ никогда не повторяются;

3) цифры $I$, $X$, $C$, $M$ могут повторяться не более трёх раз подряд;

4) если меньшая цифра стоит слева от большей, её значение вычитается из большей; вычитать можно только одну цифру $I$, $X$ или $C$; вычитаемое не может быть меньше одной десятой от уменьшаемого;

5) если цифра стоит справа от большей или равной, их значения складываются;

6) цифры в записи числа располагаются слева направо в порядке невозрастания их числового значения за исключением случаев вычитания.

Например, римская запись $MMXXVI$ корректна обозначает число 2026, а запись $MDDIVXXX$ некорректна.

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

Текстовый файл состоит из заглавных букв латинского алфавита - цифр римской системы счисления $I$, $V$, $X$, $L$, $C$, $D$, $M$. Найдите в файле все непрерывные последовательности символов, являющиеся корректными римскими записями чисел, которые невозможно расширить влево или вправо (то есть символы слева и справа от последовательности, при их наличии, не могут быть частью этой римской записи). Каждое найденное число последовательно обрабатывается по следующим правилам:

1. Вычисляется десятичное значение числа.

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

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

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

Примечание. В римской системе счисления приняты следующие правила:

1) в качестве цифр используют заглавные латинские буквы $I$, $V$, $X$, $L$, $C$, $D$, $M$, числовое значение которых 1, 5, 10, 50, 100, 500 и 1000 соответственно;

2) цифры $V$, $L$, $D$ никогда не повторяются;

3) цифры $I$, $X$, $C$, $M$ могут повторяться не более трёх раз подряд;

4) если меньшая цифра стоит слева от большей, её значение вычитается из большей; вычитать можно только одну цифру $I$, $X$ или $C$; вычитаемое не может быть меньше одной десятой от уменьшаемого;

5) если цифра стоит справа от большей или равной, их значения складываются;

6) цифры в записи числа располагаются слева направо в порядке невозрастания их числового значения за исключением случаев вычитания.

Например, римская запись $MMXXVI$ корректна обозначает число 2026, а запись $MDDIVXXX$ некорректна.

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

Сервер выполняет запросы на передачу данных, при этом сведения о каждом выполненном запросе (время регистрации, идентификатор клиента и объём переданных данных) сохраняются в журнале работы, а сам запрос — в специальном разделе памяти сервера, имеющем ограниченный объём. Каждый раз, когда в специальном разделе остаётся недостаточно свободной памяти, сервер создаёт резервную копию всех накопленных там данных, после чего освобождает раздел и продолжает выполнение запросов. Напишите программу для обработки журнала работы сервера и с её помощью определите идентификатор устройства, с которого на сервер был передан наибольший суммарный объем данных начиная с 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.

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

В период сбора урожая на винограднике работают $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.

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

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

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

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

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

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

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

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

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

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

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

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

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

Вместимость всех автобусов фиксирована и составляет $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.

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

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

Вместимость всех автобусов фиксирована и составляет $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

При таких исходных данных максимальная длина очереди перед прибытием автобуса составит 5 человек: в минуту 15 пассажир, прибывший в минуту 10, уедет на автобусе, поэтому к минуте 35 в очереди останутся пассажиры, прибывшие в минуты 12, 15, 20, 25 и 30. Пассажир, прибывший в минуту 15, дважды не сможет сесть и уедет на такси, прождав 20 минут.

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

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

Вдоль тоннеля длиной 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.

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

Вдоль тоннеля длиной 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.

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

В сувенирной мастерской есть $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.

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

В сувенирной мастерской есть $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.

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

В игровом клубе проводится серия из $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.

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