При проведении эксперимента заряженные частицы попадают на чувствительный экран, представляющий из себя матрицу размером 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 <= 8:
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)])
Ответ: 26 97586.
Приведем решение Юрия Лысакова на языке Python.
f = open('26.txt')
f.readline()
a = []
for i in f:
a.append([int(str(i).split()[0]), int(str(i).split()[1])])
a.sort(key=lambda x: x[0])
max1 = 0
ii = 0
while ii < len(a):
b = []
z = a[ii][0]
while a[ii][0] == z:
b.append(a[ii][1])
ii += 1
if ii >= len(a):
break
b.sort()
m = 1
for j in range(len(b)-1):
if b[j+1] - b[j] <= 8:
m += b[j+1] - b[j]
else:
if m >= max1:
max1 = m
nn = a[ii - 1][0]
m = 1
if m >= max1:
max1 = m
nn = a[ii - 1][0]
print(max1,nn)
Приведем решение Юрия Красильникова на языке Python.
a = [tuple(map(int,s.split())) for s in open('26.txt')][1:]
a = sorted(set(a)) # избавляемся от повторов и сортируем
# в данной задаче избавляться от повторов было необязательно
maxlen = 0 # максимальная длина
b = a[0] # начало первой линии
for i in range(1,len(a) + 1):
if i == len(a) or a[i][0] != a[i-1][0] or a[i][1] - a[i-1][1] > 8: # линия кончилась
l = a[i-1][1] - b[1] + 1 # длина линии
if l >= maxlen: # линия не короче прежнего максимума
row = b[0] # запоминаем ряд
maxlen = l # запоминаем длину линии
if i < len(a): b = a[i] # начало новой линии
print(maxlen,row)