Задание EGEINF6689F3: Сортировка, отбор и моделирование

Решение.

Сохраним приложенный текстовый файл под именем data.txt. Первая строка задаёт параметры задачи; её нельзя считать обычной записью данных. В программе нумерация элементов списка начинается с нуля, а номера из условия сохраняются без сдвига.

В файле N = 9990 занятых мест, M = 99938 рядов и K = 6660 мест в каждом ряду. Для каждого номера места c найдём номер первого занятого кресла f[c]. Если весь столбец свободен, положим f[c] = M + 1.

Пара мест c и c + 1 в ряду r подходит ровно тогда, когда r < f[c] и r < f[c + 1]. Эти неравенства одновременно гарантируют, что сами покупаемые кресла и все кресла перед ними свободны. Самый дальний допустимый ряд для этой пары: r = min(f[c], f[c + 1]) − 1. Значение 0 означает, что подходящего ряда для пары нет.

Перебираем все K − 1 соседние пары. Сначала максимизируем номер ряда. При равенстве выбираем наибольший правый номер места. Так явно соблюдается приоритет обоих критериев. За пределами мест 1…K пары не рассматриваются.

Для каждой пары взят её предельный ряд, поэтому более дальний ответ невозможен: он пересечёт первое занятое кресло хотя бы одного из двух столбцов. Время O(N + K), память O(K); строить всю огромную матрицу зала не требуется.

Полная программа на Python:

with open("data.txt", encoding="utf-8-sig") as f:
    n, rows, seats = map(int, f.readline().split())
    first = [rows + 1] * (seats + 1)
    for _ in range(n):
        r, s = map(int, f.readline().split())
        first[s] = min(first[s], r)
best_row = 0
best_seat = 0
for left in range(1, seats):
    r = min(first[left], first[left + 1]) - 1
    s = left + 1
    if r > best_row or (r == best_row and s > best_seat):
        best_row, best_seat = r, s
print(best_row, best_seat)

Проверка результата.

У выбранной пары левое место 5642, правое 5643. Первые занятые ряды этих столбцов: 9992 и 99939. Поэтому min(9992, 99939) − 1 = 9991. В ответе указываем правое место 5643.

Ответ: 9991 5643.