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