При проведении эксперимента заряженные частицы попадают на чувствительный экран, представляющий из себя матрицу размером 100 000 на 100 000 точек. При попадании каждой частицы на экран в протоколе фиксируются координаты попадания: номер ряда (целое число от 1 до 100 000) и номер позиции в ряду (целое число от 1 до 100 000).
Точка экрана, в которую попала хотя бы одна частица, считается светлой, точка, в которую ни одна частица не попала, — тёмной.
При анализе результатов эксперимента рассматривают изолированные точки.
Точка называется изолированной, если эта точка светлая (независимо от того, сколько частиц в неё попало), а другие светлые точки в том же ряду либо отсутствуют, либо находятся на расстоянии более 500.
Вам необходимо по заданному протоколу определить наибольшее количество изолированных точек, расположенных в одном ряду, и номер ряда, в котором это количество встречается. Если таких рядов несколько, укажите максимально возможный номер.
Входные данные.
Первая строка входного файла содержит целое число N — общее количество частиц, попавших на экран. Каждая из следующих N строк содержит 2 целых числа: номер ряда и номер позиции в ряду.
В ответе запишите два целых числа: сначала максимальное количество изолированных точек в одном ряду, затем — номер ряда, в котором это количество встречается.
Ответ:
Приведём решение на языке Python.
f = open('26.txt')
N = int(f.readline())
matrix = [[] for i in range(100001)]
n_row = {}
maxi = 0
for i in f:
row, cell = map(int, i.split())
if cell not in matrix[row]:
matrix[row].append(cell)
for i in range(1, 100001):
if matrix[i]:
current = [-100001] + sorted(matrix[i]) + [100001]
tmp = sum(current[j] - current[j-1] > 500 and current[j+1] - current[j] > 500 for j in range(1, len(current) - 1))
maxi = max(maxi, tmp)
n_row[i] = tmp
print(maxi, list(dict(sorted(n_row.items(), key=lambda n_row:n_row[1])))[-1])
Ответ: 20; 58612.
Приведём решение Юрия Красильникова на языке Python.
screen=set([tuple(map(int,s.split())) for s in open('26.txt')][1:])
points=sorted(screen)
rows={}
for x in points: rows[x[0]]=rows.get(x[0],[])+[x[1]]
ans=[]
for r in rows:
k=0
for i in range(len(rows[r])):
if (i==0 or rows[r][i]-rows[r][i-1]>500) and (i==len(rows[r])-1 or rows[r][i+1]-rows[r][i]>500): k+=1
ans.append((k,r))
ans.sort()
print(*ans[-1])