При проведении эксперимента заряженные частицы попадают на чувствительный экран, представляющий из себя матрицу размером 100 000 на 100 000 точек. При попадании каждой частицы на экран в протоколе фиксируются координаты попадания: номер ряда (целое число
Точка экрана, в которую попала хотя бы одна частица, считается светлой, точка, в которую ни одна частица не попала, — тёмной.
При анализе результатов эксперимента рассматривают линии. Линией называют группу светлых точек, расположенных в одном ряду подряд, то есть без тёмных точек между ними. Линия должна содержать не менее
Вам необходимо по заданному протоколу определить наибольшее количество линий, расположенных в одном ряду, и номер ряда, в котором это количество встречается. Если таких рядов несколько, укажите максимально возможный номер.
Входные данные.
Первая строка входного файла содержит целое число N — общее количество частиц, попавших на экран. Каждая из следующих
В ответе запишите два целых числа: сначала максимальное количество линий в одном ряду, затем — номер ряда, в котором это количество встречается.
Ответ:
Приведем решение на языке Python.
f = open('26.txt').readlines()[1:]
Sl = {i: [] for i in range(1, 10**5 + 1)}
for i in f:
ind, v = map(int, i.split())
Sl[ind] += [v]
def func(v):
st = ''
for x, y in zip(v, v[1:]):
st += '*' if x + 1 == y else '* '
return len([1 for s in (st + '*').split() if len(s) >= 3])
Sl = {i: func(sorted(set(v))) for i, v in Sl.items()}
print((t:=max(Sl.values())),\
list(Sl.keys())[::-1][list(Sl.values())[::-1].index(t)])
Ответ: 7 97924.
Приведем решение Юрия Красильникова на языке Python.
a=[tuple(map(int,s.split())) for s in open('26.txt')][1:]
a=sorted(set(a)) # избавляемся от повторных попаданий и сортируем
dic={}
l=1
for i in range(1,len(a)):
if a[i][0]==a[i-1][0] and a[i][1]-a[i-1][1]==1:
l+=1 # считаем длину линии
else:
if l >= 3: dic[a[i-1][0]]=dic.get(a[i-1][0],0)+1 # кол-во линий длиной 3 и более
l=1
if l >= 3: dic[a[-1][0]]=dic.get(a[-1][0],0)+1 # последняя линия
mdv=max(dic.values()) # макс. количество линий в ряду
print(mdv,max([x for x in dic if dic[x]==mdv]))