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

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

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

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

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

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

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

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

7

40 3

40 6

60 33

50 125

50 128

50 64

50 67

Условию задачи удовлетворяют три пары чисел: 40 и 4, 50 и 126, 50 и 65. Ответ для приведённого примера: 50 65.

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

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

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

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

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

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

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

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

100 4

80

30

50

40

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

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

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

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

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

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

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

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

5

43

40

32

40

30

Пример входного файла приведён для пяти коробок и случая, когда минимальная допустимая разница между длинами сторон подходящих коробок составляет 3 единицы. При таких исходных данных условию задачи удовлетворяют наборы коробок с длинами сторон 30, 40 и 43 или 32, 40 и 43 соответственно, т.е. количество коробок равно 3, а длина стороны самой маленькой коробки равна 32.

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

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

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

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

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

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

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

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

5 4

39 55

40 42

44 44

40 55

50

Пример входного файла приведён для случая пяти коробок красного цвета и четырёх коробок синего цвета, когда минимальная допустимая разница между длинами сторон коробок, подходящих для упаковки «матрёшкой», составляет 3 единицы. При таких исходных данных условию задачи удовлетворяют наборы коробок с длинами сторон 39, 42, 50 и 55 или 40, 44, 50 и 55 соответственно, т. е. количество коробок равно 4, а длина стороны самой маленькой коробки равна 40.

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

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

Входной файл содержит информацию о заявках граждан, обращающихся во многофункциональный центр (МФЦ) в течение календарных суток. В заявке указаны время начала и время окончания приёма специалистом (в минутах от начала суток).
Рабочие места специалистов МФЦ (окна) пронумерованы натуральными числами начиная с 1. Приём одного гражданина ведёт свободный специалист в окне с минимальным номером. Новый посетитель может обратиться к освободившемуся специалисту начиная со следующей минуты после завершения приёма предыдущего. Если в момент обращения в МФЦ свободных специалистов нет, то гражданин уходит. Определите, сколько граждан смогут попасть на приём в МФЦ в течение 24 ч, и каков номер окна специалиста, который начнёт принимать посетителя последним. Если таких окон несколько, укажите наименьший номер окна.

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

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

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

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

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

2

5

30 60

40 100

59 60

61 100

101 144

При таких исходных данных воспользоваться услугами МФЦ смогут первый, второй, четвёртый и пятый граждане. Наименьший номер окна, где последний из граждан будет принят специалистом, - 1, так как будут свободны окна 1 и 2.

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

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

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

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

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

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

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

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

7 7 8

1 1

6 6

5 5

6 7

4 4

2 2

3 3

При таких исходных данных ответом является пара чисел 5 и 6. Условию задачи удовлетворяют места 6 и 7 в ряду 5: перед креслами и 7 нет занятых мест и это первая из двух возможных пар в этом ряду. В рядах 6 и 7 искомую пару найти нельзя. Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

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

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

В супермаркете проводится акция «каждый четвертый товар в чеке за полцены». Покупатель расположил товары на ленте так, чтобы заплатить за покупку несколькими чеками как можно меньше с учетом проходящей акции. Известно, что кассовый аппарат сортирует покупки так, чтобы условие акции соблюдалось и при этом итоговая стоимость покупки была максимально возможной.

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

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

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

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

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

4

80

30

50

40

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

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

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

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

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

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

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

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

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

5

10 150

100 120

131 170

150 180

120 130

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

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

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

На производство штук изделий $N$ деталей должны быть отшлифованы и окрашены. Для каждой детали известно время её шлифовки и время окрашивания. Детали пронумерованы начиная с единицы. Параллельная обработка деталей не предусмотрена.

На ленте транспортёра имеются $N$ мест для каждой из $N$ деталей. Места для деталей пронумерованы начиная с единицы.

На ленте транспортёра детали располагают по следующему алгоритму:

• все $2*N$ чисел, обозначающих время окрашивания и шлифовки для $N$ деталей, упорядочивают по возрастанию;

• если минимальное число в этом упорядоченном списке — это время шлифовки конкретной детали, то деталь размещают на ленте транспортёра на первое свободное место о её начала;

• если минимальное число — это время окрашивания, то деталь размещают на первое свободное место от конца ленты транспортера;

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

Этот алгоритм применяется последовательно для размещения всех $N$ деталей.

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

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

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

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

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

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

5 

30 50 

100 155 

150 170 

10 160 

120 55 

При таких исходных данных порядок расположения деталей на ленте транспортёра следующий: 4, 1, 2, 3, 5. Последней займёт своё место на ленте деталь 3. При этом до неё будут отшлифованы три детали.

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

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

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

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

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

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

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

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

7 7 8

1 1

6 6

5 5

6 7

4 4

2 2

3 3

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

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

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

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

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

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

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

В первой строке входного файла находится число $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 задачи). Ответом является пара чисел: 50; 3.

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

Файл к заданию: https://drive.google.com/file/d/11OGYMUR9VVhFYzsxpRk3mxAxP7GVVs_A/view?usp=sharing

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

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

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

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

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

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

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

7 

40 3 

40 5

60 33 

50 125 

50 128 

50 64 

50 66 

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

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

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

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

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

В первой строке входного файла находится число $N$, обозначающее количество студентов (целое положительное число, не превышающее 10000). Каждая из следующих $N$ строк содержит 5 чисел через пробел: ID студента (целое положительное число, не превышающее 100000) и четыре оценки, полученные им за сессию. Количество получателей стипендии равно целой части от деления $N$ на 4. Гарантируется, что хотя бы один студент имеет более двух «двоек». Во входном файле все 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 2.

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

Файл к заданию: https://drive.google.com/file/d/11KzQQRtfDaXkUn3uXNp9zCdVMUe5nS8t/view?usp=sharing

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

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

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

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

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

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

5

43

40

32

40

30

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

При таких исходных данных условию задачи удовлетворяют наборы коржей с диаметрами 30, 40 и 43 или 32, 40 и 43 соответственно, т.е. количество коржей равно 3, а диаметр самого маленького коржа равен 32.

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

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

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

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

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

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

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

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

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

9 6 7

1 1

2 4

3 6

6 1

4 3

5 5

5 2

6 6

4 7

При таких исходных данных условию задачи удовлетворяют места (ряд, место): 5, 1: 4, 2; 6, 4; 4, 5. Перед этими местами три подряд кресла свободны.

Ответом является пара чисел 4 и 3.

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

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

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

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

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

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

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

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

3 220

60 70 80

63 60 90

50 80 100

При таких исходных данных проходной балл равен 230, полупроходной 215, на оставшееся одно место будет зачислен абитуриент, набравший в сумме 215 баллов и получивший по математике 95 баллов. Ответ для приведённого примера: 215 95.

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

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

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

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

Найдите суммарную стоимость оставшихся товаров артикула - лидера продаж и укажите этот артикул.

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

В первой строке входного файла находится число $N$ — количество товаров в базе данных магазина (натуральное число, не превышающее 10000). В каждой из следующих $N$ строк находится три числа, разделенных пробелом: артикул товара (натуральное число до 100000), его цена (натуральное число до 10000) и статус (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 рублей. Больше всего продано товара вида 10. В продаже остался один такой товар. Условию задачи удовлетворяет ответ 100 10.

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

Файл к заданию: https://drive.google.com/file/d/1ZeS4VEPsrTb3EOQG-xce2z9brs127hNa/view?usp=sharing

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

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

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

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

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

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

5

10 150

100 120

131 170

150 180

120 130

При таких исходных данных можно провести максимум два мероприятия, например, мероприятия по заявкам 2 и 4. Максимальный перерыв между двумя последними мероприятиями составит 30 мин., если состоятся мероприятия по заявкам 2 и 5.

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

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

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

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

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

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

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

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

Всего на сервер должно быть передано 596000 Кбайт данных: 158000, 122000, 182000 и 134000 Кбайт от клиента идентификатором 101, 202, 303 404 соответственно. Ответ для приведённого примера: 134000 220000.

Типовой пример имеет иллюстративный характер.

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

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

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

Всего на сервер должно быть передано 596000 Кбайт данных: 158000, 122000, 182000 и 134000 Кбайт от клиентов с идентификаторами 101, 202, 303 и 404 соответственно. Ответ для приведённого примера: 606 220000

Типовой пример имеет иллюстративный характер.

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

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

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

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

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

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

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

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

2 6

30 60 A

65 1000 A

65 1000 В

1010 1300 B

65 900 A

905 1100 A

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

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

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

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

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

Первая строка входного файла (журнала работы сервера) содержит два натуральных числа: $N$ ($N< 1 000 000$) - количество строк в журнале и $K$ ($K < 1 000 000$) - вместимость специального раздела памяти сервера в Кбайт. Каждая из следующих $N$ строк содержит информацию об одном выполненном запросе: время регистрации запроса в формате ЧЧ:ММ:CC (часы, минуты, секунды) и два натуральных числа: $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 (в объёме 90 000 Кбайт), в 21:21:21 (в объёме 122000 Кбайт) и в 23:23:23 (в объёме 120000 Кбайт).

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

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

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

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

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

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

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

В первой строке входного файла находится число $N$ — количество товаров в базе данных магазина (натуральное число, не превышающее 10000). В каждой из следующих $N$ строк находится три числа, разделённых пробелом: артикул товара (натуральное число, не превышающее 100000), его цена (натуральное число, не превышающее 10000) и статус (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 рублей. Больше всего было продано товара вида 10. В продаже остался один такой товар. Условию задачи удовлетворяет ответ 200 1.

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

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

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

1) она была обработана после детали с самым высоким баллом в партии;

2) при этом показатель качества детали, обработанной сразу после искомой, отличается (в ту или иную сторону) от её балла не более чем на $K$ баллов.

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

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

В первой строке входного файла дано натуральное число $N$ ($3 < N< 100 000$) - количество деталей в партии. Вторая строка входного файла содержит три натуральных числа, разделённых пробелами: числа $A$, $B$ ($A < B$) - границы диапазона допустимых значений качества для поиска особенной детали и число - показатель требуемой разности баллов особенной детали и детали, следующей за ней в исходном списке. В следующих $N$ строках даны натуральные числа, не превышающие 1000, обозначающие баллы деталей в порядке, записанным в журнале качества.

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

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

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

12

70 90 5

65

72

88

84

91

77

90

85

80

73

88

83

При таких исходных данных в партии особенные детали с показателями качества 90, 85 и 88 баллов; деталь с показателем качества 90 баллов занимает в рейтинге место 2.

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

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

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

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

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

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