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

Решение.

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

В файле N = 9996, M = 99931, K = 3332. Кресла перед выбранным местом имеют тот же номер места, поэтому каждую вертикальную колонку рассматриваем отдельно. Сам покупаемый билет должен соответствовать свободному креслу.

В список занятых рядов каждой колонки добавим условные границы 0 и M + 1. Между соседними границами a < b свободны все ряды a + 1…b − 1. Если b − a ≥ 2, лучший покупаемый ряд в этом промежутке равен b − 1: перед ним подряд свободны b − a − 2 кресла. Само покупаемое кресло в это количество не включаем.

Покупка в более раннем ряду того же промежутка уменьшает число свободных кресел перед ним. Поэтому достаточно проверить последние свободные кресла всех промежутков. Границы 0 и M + 1 учитывают начало и конец зала, в том числе полностью пустую колонку.

Сначала максимизируем количество свободных кресел впереди, затем минимизируем номер ряда. Вторым числом выводим найденное количество свободных кресел, а не номер места. Полнота следует из перебора всех свободных промежутков. Сложность O(N log N + K), память O(N + K).

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

with open("data.txt", encoding="utf-8-sig") as f:
    n, rows, seats = map(int, f.readline().split())
    occupied = [set() for _ in range(seats + 1)]
    for _ in range(n):
        r, s = map(int, f.readline().split())
        occupied[s].add(r)
best = None
for s in range(1, seats + 1):
    borders = [0] + sorted(occupied[s]) + [rows + 1]
    for a, b in zip(borders, borders[1:]):
        if b - a >= 2:
            candidate = (b - a - 2, -(b - 1), -s)
            if best is None or candidate > best:
                best = candidate
count, negative_row, negative_seat = best
print(-negative_row, count)

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

Оптимальная колонка имеет номер 620. Соседние занятые или условные граничные ряды: 34708 и 68218. Покупаемый ряд 68218 − 1 = 68217; перед ним свободны 68218 − 34708 − 2 = 33508 кресел подряд. Все остальные промежутки проверены тем же правилом.

Ответ: 68217 33508.