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

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

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

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

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

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

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

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

При таких исходных данных ответом является пара чисел \(3\) и \(12\) (места №3, 4 и 5 в ряду №3).

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

fd =  open('26_22577.txt')
M, N, K, V = map(int, fd.readline().split())
seats = [[0 for i in range(K+1)] for j in range(M + 1)]
for line in fd:
    r, s = map(int, line.split())
    seats[r][s] = 1

f = True
for row in range(V+1, M+1):
    if not f:
        break
    for s in range(K, 2, -1):
        if sum(seats[x][s] for x in range(row)) >= V \
            and sum(seats[x][s-1] for x in range(row)) >= V \
            and sum(seats[x][s-2] for x in range(row)) >= V:
            print(row, 3*s - 3)
            f = False
            break