Задание 26 ЕГЭ информатика: № 26002. Апробация

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

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

2602.txt 110,7 КБ

with open('2602.txt') as file:
    N, M, K = map(int, file.readline().split())
    data = [list(map(int, line.split())) for line in file]

# === Ответы === #
max_row = 0
min_seat = 0
# ===       === #

# Первый занятый ряд для каждого места
min_row = [M + 1] * (K + 2)

# Определяем первый занятый ряд для каждого места
for row, seat in data:
    if row < min_row[seat]:
        min_row[seat] = row

# Проходимся по всем местам и ищем максимальный доступный ряд
for seat in range(1, K):
    # Допустимый ряд: на 1 меньше, чем первый занятый
    accept_row = min(min_row[seat], min_row[seat + 1]) - 1
    if accept_row > max_row or (accept_row == max_row and seat < min_seat):
        max_row = accept_row
        min_seat = seat

print(f'Наибольший номер ряда: {max_row}')
print(f'Наименьший номер места: {min_seat}')

Рекомендуемые статьи