Задание 26. Информатика. ЕГЭ Статград. База. 12.05.2025

При бронировании билетов на теплоход известно, какие каюты на жилой палубе уже заняты. Палуба представима в виде сетки из \(M\) рядов, каждый из которых содержит \(K\) кают. Необходимо забронировать две соседние каюты в таком ряду, чтобы в нём было забронировано не менее \(35\) кают, а в двух соседних рядах (сзади и спереди) было как можно больше свободных кают, причём крайние ряды для брони рассматривать не следует. Если существует несколько вариантов бронирования, удовлетворяющих этим условиям, следует выбрать ряд с наибольшим номером. В ответе запишите два целых числа: искомый номер ряда и суммарное количество забронированных кают в соседних (относительно выбранных мест) рядах. Нумерация рядов и кают ведётся с \(1.\) Гарантируется, что бронь, соответствующая условиям, возможна.

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

В первой строке входного файла находятся три числа: \(N\) – количество занятых кают на палубе (целое положительное число, не превышающее \(100~000),\) \(M\) – количество рядов (целое положительное число, не превышающее \(10~000)\) и \(K\) – количество кают в каждом ряду (целое положительное число, не превышающее \(1~000~000).\) В следующих \(N\) строках находятся пары натуральных чисел: номер ряда и номер занятой каюты соответственно (первое число не превышает значения \(M,\) а второе – \(K).\)

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

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

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

\(7 7 8\)
\(1 \,\, 1\)
\(6 \,\, 6\)
\(5 \,\, 5\)
\(6 \,\, 7\)
\(4 \,\, 4\)
\(2 \,\, 2\)
\(3 \,\, 3\)

При таких исходных данных и отсутствии ограничений на количество забронированных в ряду кают ответом является пара чисел \(6\) и \(1.\)

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

fd = open('26.txt')
N, M, K = map(int, fd.readline().split())
rows = {}
for line in fd:
    m, k = map(int, line.split())
    if rows.get(m):
        rows[m].append(k)
    else:
        rows[m] = [k]

m_ans, br = 0, float('inf')

for i in range(2, M):
    r = rows.get(i, [])
    if len(r) > 32:
        r.sort()
        if any(y - x > 2 for x, y in zip(r, r[1:])):
            t = len(rows.get(i-1, [])) + len(rows.get(i+1, []))
            if t <= br:
                m_ans = i
                br = t

print(m_ans, br)