При проведении эксперимента заряженные частицы попадают на чувствительный экран, представляющий из себя матрицу размером 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):
if not V: return -1
ma = -1
for i, x in enumerate(V):
for v0, v1 in zip(V[i:], V[i+1:]):
if v1 - v0 <= 9:
ma = max(ma, v1 - x + 1)
else: break
return ma
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)])
Ответ: 32 79316.
Приведем решение Юрия Ворошилова на языке Python.
f = open('26.txt')
n = int(f.readline())
a = [list(map(int, i.split())) for i in f]
a.sort(key=lambda i: i[1])
a.sort(key=lambda i: i[0])
lmx,imx, j =0, 0, 0
for i in range(1, 10**5+1):
l=1
j+=1
while a[j+1][0]==i and a[j][0]==i and j < n-2:
if a[j+1][1]-a[j][1]<10:
l+=a[j+1][1]-a[j][1]
if l > lmx:
lmx=l
imx=i
else:
l=1
j+=1
print(lmx,imx)