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

Решение.

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

В файле 9986 пар «ряд, занятое место». Для каждого ряда соберём множество занятых мест, затем отсортируем его. Повтор одной и той же записи, если он встретится, не должен создавать дополнительное кресло.

Пусть a и b — соседние элементы отсортированного списка занятых мест одного ряда. Между ними находятся ровно b − a − 1 свободных кресел. Нам нужны ровно два: b − a = 3. Тогда свободная пара имеет номера a + 1 и a + 2, а её непосредственные соседи a и a + 3 заняты.

Важно сравнивать именно соседние занятые места: иначе внутри промежутка может находиться ещё одно занятое кресло. У начала или конца списка пара без двух занятых соседей не подходит. Условие на свободные кресла в других рядах здесь отсутствует.

Из найденных вариантов выбираем максимальный номер ряда, а внутри него минимальное a + 1. Перебор всех соседних элементов полон, поскольку у любой требуемой свободной пары два занятых соседа обязательно последовательны в отсортированном списке. Сортировки занимают O(N log N), память O(N).

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

from collections import defaultdict
with open("data.txt", encoding="utf-8-sig") as f:
    n = int(f.readline())
    occupied = defaultdict(set)
    for _ in range(n):
        r, s = map(int, f.readline().split())
        occupied[r].add(s)
best_row = 0
best_seat = 0
for r, seats in occupied.items():
    seats = sorted(seats)
    for a, b in zip(seats, seats[1:]):
        if b - a == 3:
            s = a + 1
            if r > best_row or (r == best_row and s < best_seat):
                best_row, best_seat = r, s
print(best_row, best_seat)

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

Найдено 2002 подходящих пар по всему файлу. В выбранном ряду 79936 заняты кресла 78781 и 78784, между ними свободны 78782 и 78783. Разность номеров занятых кресел 78784 − 78781 = 3. Среди подходящих пар этого максимального ряда минимальное левое место равно 78782.

Ответ: 79936 78782.