Задание 26. Информатика. ЕГЭ. Статград. 28.01.2025-1
- Просмотры: 669
- Изменено: 2 февраля 2025
При проведении эксперимента заряженные частицы попадают на чувствительный экран, представляющий из себя матрицу размером \(100~000\) на \(100~000\) точек. При попадании каждой частицы на экран в протоколе фиксируются координаты попадания: номер ряда (целое число от \(1\) до \(100~000\)) и номер позиции в ряду (целое число от \(1\) до \(100~000\)). Точка экрана, в которую попала хотя бы одна частица, считается светлой, точка, в которую ни одна частица не попала, – тёмной.
При анализе результатов эксперимента рассматривают изолированные точки. Точка называется изолированной, если эта точка светлая (независимо от того, сколько частиц в неё попало), а другие светлые точки в том же ряду либо отсутствуют, либо находятся на расстоянии более \(500.\) Вам необходимо по заданному протоколу определить наибольшее количество изолированных точек, расположенных в одном ряду, и номер ряда, в котором это количество встречается. Если таких рядов несколько, укажите максимально возможный номер.
Входные данные
Первая строка входного файла содержит целое число \(N\) – общее количество частиц, попавших на экран. Каждая из следующих \(N\) строк содержит \(2\) целых числа: номер ряда и номер позиции в ряду. В ответе запишите два целых числа: сначала максимальное количество изолированных точек в одном ряду, затем – номер ряда, в котором это количество встречается.
Решение:
Python
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))
Ответ: \(20 \,\, 58612\)