Задание 26. Информатика. ЕГЭ. Апробация. 05.03.2025
- Просмотры: 84
- Изменено: 6 марта 2025
При онлайн-покупке билета на концерт известно, какие места в зале уже заняты. Необходимо купить два билета на такие соседние места в одном ряду, чтобы перед ними все кресла с такими же номерами были свободны, а ряд находился как можно дальше от сцены. Если в этом ряду таких пар мест несколько, найдите пару с наименьшими номерами. В ответе запишите два целых числа: искомый номер ряда и наименьший номер места в найденной паре. Нумерация рядов и мест ведётся с \(1.\) Гарантируется, что хотя бы одна такая пара в зале есть.
Входные данные
В первой строже входного файла находятся три числа: \(N\) — количество занятых мест в зале (целое положительное число, не превышающее \(10~000),\) \(M\) — количество рядов (целое положительное число, не превышающее \(100~000)\) и \(K\) — количество мест в каждом ряду (целое положительное число, не превышающее \(100~000).\) В следующих \(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\) искомую пару найти нельзя.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Решение:
Python
base = ''
fd = open(base + '26.txt')
N, M, K = [int(x) for x in fd.readline().split()]
seats = [M] * (K + 1)
for line in fd:
row, seat = [int(x) for x in line.split()]
seats[seat] = min(seats[seat], row)
min_seat = float('inf')
max_row = 0
for s in range(1, K):
row = min(seats[s] - 1, seats[s+1] - 1)
if row > max_row:
max_row = row
min_seat = s
print(max_row, min_seat)
Ответ: \(21028 \,\, 6660\)