ЕГЭ-26. Обработка массива целых чисел. Сортировка

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

Алгоритм формирования рейтинга выглядит следующим образом:

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

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

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

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

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

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

5
800 120
150 200
250 300
60 100
180 220

Пример организации данных приведён для пяти смартфонов.

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

(ЕГЭ-2025) На соревнованиях по спортивному ориентированию каждый участник должен пройти маршрут, посещая контрольные точки. Все контрольные точки пронумерованы натуральными числами, начиная с 1. В начале сезона соревнований каждому спортсмену присваивается уникальный номер -- натуральное число, не превышающее 1 000 000. Жюри фиксирует факт прохождения спортсменом контрольной точки. На разных этапах соревнований спортсмен может посетить одну и ту же контрольную точку в произвольном порядке несколько раз или не посетить совсем. Тренер в конце сезона анализирует результаты этапов соревнования, чтобы выявить контрольную точку, которую посетило наибольшее число спортсменов с идущими подряд номерами. Определите максимальное число спортсменов с идущими подряд номерами и номер найденной контрольной точки. Если таких групп спортсменов несколько, укажите наименьший номер посещённой группой контрольной точки.

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

точку, и номер этой точки.

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

9
41 3
43 125
50 33
42 125
42 126
42 127
41 125
50 126
42 126

Для приведённого примера точку с номером 125 посетили три спортсмена с номерами 41, 42 и 43. Ответ: 3 125.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(Л. Шастин) На склад магазина привезли N упаковок свежей продукции. Вновь привезенную продукцию сортируют по K холодильным камерам, вместимость каждой из которых равна M кг. Холодильные камеры, в свою очередь, пронумерованы от 1 до K. Фасовщики заполняют холодильные камеры последовательно, начиная с 1-й. Сначала погружают товары наибольшего объема (до тех пор, пока самый большой из оставшихся товаров влезает в холодильную камеру), стремясь заполнить текущую холодильную камеру до предела, а оставшееся свободное место начиняют товарами наименьшего объема. Гарантируется, что K камер хранения достаточно для сортировки всей продукции по описанной выше стратегии.

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

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

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

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

5
5
10
9
7
6
4
1

При таких исходных данных первая холодильная камера будет заполнена до отвала, во второй останется 3 кг свободного места, а в третьей - 0 кг. В третью же камеру и погрузят последний товар. Ответ: 3 0.

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

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

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

Каждая из следующих N строк содержит три натуральных числа, не превышающих 100 000: номер этажа, номер ряда и номер занятого места в этом ряду.

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

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

7 6
1 50 2
2 23 1
1 50 6
1 1 1
2 30 5
2 23 6
1 1 6

Для этих данных можно забронировать 4 соседних места в двух рядах: в 1-м ряду на 1-м этаже и в 23-м ряду на 2-м этаже. Ответ: 23 2.

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

Определите, сколько будет закуплено товаров типа Z и сколько денег останется.

Входные данные представлены в файле 26-62.txt следующим образом. Первая строка входного файла содержит два целых числа: N -- общее количество товаров и M -- сумма выделенных на закупку денег (в рублях). Каждая из следующих N строк содержит целое число (цена товара в рублях) и символ (латинская буква Q или Z), определяющий тип товара. Все данные в строках входного файла отделены одним пробелом.

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

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

6 110
40 Z
50 Q
50 Z
30 Z
20 Q
10 Z

В данном случае можно купить не более четырёх товаров, из них не более трёх товаров типа Z. Минимальная цена такой покупки 100 рублей (покупаем товары 10 Z, 20 Q, 30 Z, 40 Z). Останется 10 рублей. Ответ: 3 10.

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

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

Пример входного файла
7
1 2
2 3
3 6
2 4
1 3
2 5
2 4
При таких исходных данных имеется три водоема: в координатах (1, 2) и (1, 3) и в координатах (2, 4), (2, 5) и (2, 6) (это самый длинный водоем!) и с координатой (3, 6).
Ответ: 3 2.

 Файл к заданию

Для анализа читательской активности, учителя попросили детей заносить в компьютер время начала и время завершения чтения какой-либо книги. Данные автоматически переводились в миллисекунды от момента начала исследований. Если дети начали читать какую-либо книгу до начала исследования, то начальное время устанавливалось равным 0. Если дети к концу исследования не успевали дочитать какую-либо книгу, то конечное время устанавливалось равным 0.
Необходимо определить наибольшее количество книг, которые дети читали одновременно в течение суток, начиная с момента K, и суммарное время, в течение которого читалось это максимальное количество книг.

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

Пример входного файла (для заданного диапазона от 1000 до 6000):
6 1000
1300 2200
0 3700
1300 5700
0 0
5000 0
1800 3400
В данном случае наибольшее число книг (5) читалось в интервале времени между 1800 и 2200.

Ответ: 5 400.

Файл к заданию

Магазин производит закупку болтов (bolt), гаек (nut), гвоздей (pin), шайб (shim) и винтов (screw), на которую выделена определённая сумма денег. У метизного завода есть в наличии различные модификации этих изделий по розничной цене. При покупке менеджер руководствуется следующими правилами:

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

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

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

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

Примеры

№	Входные данные	Выходные данные
1	6 1650 600 screw 750 bolt 750 shim 450 pin 300 nut 150 bolt	2 0

 
Файл к заданию

Ученые, работающие с элементарными частицами, часто проводят эксперименты по их сталкиванию. Для этого на коллайдере их разгоняют до больших скоростей, а потом регистрируют треки частиц. В качестве результатов одного из таких экспериментов получены данные работы детектора ALICE в виде координат мест регистрации центров частиц на двумерной квадратной матрице и размеров самих частиц. Матрица имеет размеры 1000 на 1000 точек. 
Вам необходимо по полученным результатам эксперимента определить точку матрицы, в которой было зарегистрировано максимальное количество частиц.
Для упрощения, форму частицы считать квадратом, сторона которого всегда имеет нечетный размер. 

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

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

Пример входного файла:
5
2 3 3
3 6 5
8 4 1
7 5 5
6 8 3

Ответом для данного примера будет пара чисел 12 3

Скачать файл

В период засухи существует опасность лесных пожаров. Чем раньше получится ликвидировать пожар, тем меньший вред он нанесет. Поэтому для предотвращения больших пожаров создана мобильная пожарная бригада. Для мониторинга ситуации проводится аэросъемка местности. Территория разбивается на квадратные участки (клетки), сторона каждой из которых равна 1 км. Клетки нумеруются по принципу: столбцы обозначаются буквами латинского алфавита, а строки — числами. Клетка может содержать лес или пустое пространство. Для ликвидации пожара высылается пожарная бригада, которую доставляют вертолетом максимально близко к точке возгорания. Но приземлиться в любой точке местности вертолет не может. Считается, что точка доступна для посадки, если она находится в центре квадрата из свободных клеток со стороной размера 5, расположенного целиком внутри территории. Необходимо найти количество подходящих под условие задачи точек посадки и расстояние до максимально близкой к точке возгорания клетки, в которую возможно совершить посадку. Если таких клеток найдено несколько, укажите клетку с лексикографически минимальным обозначением столбца и минимальным номером ряда.

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

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

Пример входного файла:
4
A 1
C 1
B 2
B 4
B 3
Если считать, что территория ограничена набором из 7 букв от А до G и 7 строк, то под условие посадки подойдут две клетки: Е 4 и Е 5.
Максимально близкая к точке возгорания клетка, доступная для посадки – это Е 4. Расстояние от Е4 до В3 3.16... Округленное до целого значения 3.
Ответ для примера: 2 3

Скачать файл