При проведении эксперимента заряженные частицы попадают на чувствительный экран, представляющий из себя матрицу размером 100 000 на 100 000 точек. При попадании каждой частицы на экран в протоколе фиксируются координаты попадания: номер ряда (целое число от 1 до 100 000) и номер позиции в ряду (целое число от 1 до 100 000).
Точка экрана, в которую попала хотя бы одна частица, считается светлой, точка, в которую ни одна частица не попала, — тёмной.
При анализе результатов эксперимента рассматривают изолированные точки.
Точка называется изолированной, если эта точка светлая (независимо от того, сколько частиц в неё попало), а другие светлые точки в том же ряду либо отсутствуют, либо находятся на расстоянии более 1000.
Вам необходимо по заданному протоколу определить наибольшее количество изолированных точек, расположенных в одном ряду, и номер ряда, в котором это количество встречается. Если таких рядов несколько, укажите максимально возможный номер.
Входные данные.
Первая строка входного файла содержит целое число N — общее количество частиц, попавших на экран. Каждая из следующих N строк содержит 2 целых числа: номер ряда и номер позиции в ряду.
В ответе запишите два целых числа: сначала максимальное количество изолированных точек в одном ряду, затем — номер ряда, в котором это количество встречается.
Ответ:
Приведём решение на языке 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]>1000) and (i==len(rows[r])-1 or rows[r][i+1]-rows[r][i]>1000):
k+=1
ans.append((k,r))
ans.sort()
print(*ans[-1])
Ответ: 17; 99418.