Задание 26. Информатика. ЕГЭ. Статград. 28.01.2025-1

При проведении эксперимента заряженные частицы попадают на чувствительный экран, представляющий из себя матрицу размером \(100~000\) на \(100~000\) точек. При попадании каждой частицы на экран в протоколе фиксируются координаты попадания: номер ряда (целое число от \(1\) до \(100~000\)) и номер позиции в ряду (целое число от \(1\) до \(100~000\)). Точка экрана, в которую попала хотя бы одна частица, считается светлой, точка, в которую ни одна частица не попала, – тёмной.

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

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

Первая строка входного файла содержит целое число \(N\) – общее количество частиц, попавших на экран. Каждая из следующих \(N\) строк содержит \(2\) целых числа: номер ряда и номер позиции в ряду. В ответе запишите два целых числа: сначала максимальное количество изолированных точек в одном ряду, затем – номер ряда, в котором это количество встречается.

base = ''

rows = [[] for _ in range(100_001)]
fd = open(base + '26.txt')
N = int(fd.readline())

for line in fd:
    row, pos = map(int, line.split())
    if pos not in rows[row]:
        rows[row].append(pos)

q_max = 0
d_isol = {}

for i in range(1, 100_001):
    if rows[i]:
        row_work = [-600] + sorted(rows[i]) + [101_000]
        q_work = sum(row_work[j] - row_work[j-1] > 500 and \
                         row_work[j+1] - row_work[j] > 500 \
                         for j in range(1, len(row_work) - 1))
        q_max = max(q_max, q_work)
        d_isol[i] = q_work

print(q_max, max(k for k, v in d_isol.items() if v == q_max))