При проведении эксперимента заряженные частицы попадают на чувствительный экран, представляющий из себя матрицу размером 100 000 на 100 000 точек. При попадании каждой частицы на экран в протоколе фиксируются координаты попадания: номер ряда (целое число от 1 до 100 000) и номер позиции в ряду (целое число от 1 до 100 000).
Точка экрана, в которую попала хотя бы одна частица, считается светлой, точка, в которую ни одна частица не попала, — тёмной.
При анализе результатов эксперимента рассматривают изолированные точки.
Точка называется изолированной, если эта точка светлая (независимо от того, сколько частиц в неё попало), а другие светлые точки в том же ряду либо отсутствуют, либо находятся на расстоянии более 1000.
Вам необходимо по заданному протоколу определить наибольшее количество изолированных точек, расположенных в одном ряду, и номер ряда, в котором это количество встречается. Если таких рядов несколько, укажите максимально возможный номер.
Входные данные.
Первая строка входного файла содержит целое число N — общее количество частиц, попавших на экран. Каждая из следующих N строк содержит 2 целых числа: номер ряда и номер позиции в ряду.
В ответе запишите два целых числа: сначала максимальное количество изолированных точек в одном ряду, затем — номер ряда, в котором это количество встречается.
Ответ:
Решение.
Это задание ещё не решено, приводим решение прототипа.
При проведении эксперимента заряженные частицы попадают на чувствительный экран, представляющий из себя матрицу размером 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])