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

(ЕГЭ-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.

(О. Лысенков) В файле 17-436.txt содержится последовательность натуральных чисел, не превышающих 10 000. Определите количество троек элементов последовательности, в которых ровно у одного элемента первая и последняя цифра совпадают и ровно два элемента являются четырёхзначными числами, у которых цифра, находящаяся в разряде сотен, равна 2. В ответе запишите количество найденных троек чисел, затем сумму максимальных элементов таких троек. В данной задаче под тройкой подразумевается три идущих подряд элемента последовательности.

(А. Брейк) В файле 17-290.txt содержится последовательность целых чисел. Элементы последовательности могут принимать целые значения от 0 до 10 000. Запишите в ответе количество троек элементов последовательности, в которых хотя бы одно число оканчивается на 4 в пятеричной системе счисления и ни одно из чисел не имеет цифру 0 в своей шестеричной записи. Затем запишите максимальную разность между максимальным и минимальным числами в таких тройках. В данной задаче под тройкой подразумевается три идущих подряд элемента последовательности.

(Л. Евич) В файле 22-102.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно... (Условие совпадает с условием задачи из демо-варианта 2024 года). Определите максимальную продолжительность отрезка времени (в мс), в течение которого возможно одновременное выполнение четырёх процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно.

*(Г. Гутман) На ленте исполнителя МТ в соседних ячейках записана последовательность из

1000 символов, состоящая из некоторого числа блоков вида (k*'1'+k*'0'), при этом последний блок может быть неполным. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке слева от последовательности. Программа для исполнителя:

Команды движения каретки: L – влево, R – вправо, N – отсутствие сдвига, S – стоп. После выполнения программы в полученной последовательности оказалось 10 символов 1. Определите максимально возможное значение параметра k в исходной последовательности.

(В. Шубинкин) На ленте исполнителя МТ в соседних ячейках записана последовательность символов 2…20…01…1: сначала 120 двоек, затем 333 ноля и 750 единиц. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка находится на неизвестном ненулевом расстоянии слева от последовательности. Программа для исполнителя:

Команды движения каретки: L – влево, R – вправо, S – стоп. Определите количество ячеек, значения которых после выполнения программы не равны исходным.

Повтори k [Команда1 Команда2 … КомандаS]

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

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

Ответ: 5 400.

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

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

Примеры