Задание 26. Информатика. ЕГЭ 2027. Шастин. 30.09.2026

(Л. Шастин) На автоматизированном складе товары хранятся на стеллажах (рядах). Ячейки на каждом стеллаже пронумерованы, начиная с единицы. Известно, какие ячейки на каких стеллажах уже заняты контейнерами.

Для размещения крупногабаритного оборудования требуется выделить \(15\) свободных ячеек подряд на одном стеллаже. Для формирования секции разрешается убрать ровно один контейнер. Если контейнер находится между двумя блоками свободных ячеек, то после его удаления эти блоки объединяются вместе с освободившейся ячейкой. При этом непосредственно слева и справа от сформированной секции из \(15\) свободных ячеек на том же стеллаже должны находиться занятые ячейки (для фиксации боковых перегородок).

Найдите стеллаж с наибольшим номером, на котором возможно сформировать такую секцию из \(15\) свободных ячеек. В ответе запишите два целых числа: наибольший номер стеллажа и наименьший номер ячейки (координату первой ячейки) в найденной секции из \(15\) свободных мест.

Если на подходящем стеллаже есть несколько вариантов формирования такой секции, выберите вариант с наименьшим номером начальной ячейки.

Входные данные

В первой строке входного файла находится число \(N\) — количество занятых ячеек (натуральное число, не превышающее \(20~000).\) Каждая из следующих \(N\) строк содержит два натуральных числа, не превышающих \(100~000:\) номер стеллажа и номер ячейки на этом стеллаже, в которой находится контейнер.

Выходные данные

Два целых неотрицательных числа: наибольший номер стеллажа и наименьший номер ячейки в выбранной последовательности из \(15\) свободных мест.

Типовой пример организации входных данных

\(7\)
\(25 \,\, 10\)
\(25 \,\, 15\)
\(85 \,\, 40\)
\(70 \,\, 102\)
\(70 \,\, 210\)
\(70 \,\, 213\)
\(70 \,\, 215\)

Для приведённого примера, при условии, что необходимо сформировать \(4\) свободные ячейки подряд, ответом является пара чисел: \(70; \, 211.\)

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

from collections import defaultdict

rack = defaultdict(list)
FREE_CELLS = 15
fd = open('26.txt')
N = int(fd.readline())
for line in fd:
    r, c = line.split()
    rack[int(r)].append(int(c))

ks = sorted(rack.keys(), reverse=True)
for row in ks:
    if len(rack[row]) < 2:
        continue
    ans = []
    rack[row].sort()
    ## Смотрим на ближайшие заполненные ячейки. Может уже есть 15 свободных клеток
    for a, b in zip(rack[row], rack[row][1:]):
        if b - a == FREE_CELLS + 1:
            ans.append(a + 1)
    ## Ищем возможность освободить 1 ячейку
    if len(rack[row]) > 2:
        for a, b in zip(rack[row], rack[row][2:]):
            if b - a == FREE_CELLS + 1:
                ans.append(a + 1)
    if ans:
        print(row, min(ans))
        break