РЕШУ ЕГЭ — информатика

Задания

При проведении эксперимента заряженные частицы попадают на чувствительный экран, представляющий из себя матрицу размером 100 000 на 100 000 точек. При попадании каждой частицы на экран в протоколе фиксируются координаты попадания: номер ряда (целое число от 1 до 100 000) и номер позиции в ряду (целое число от 1 до 100 000).

Точка экрана, в которую попала хотя бы одна частица, считается светлой, точка, в которую ни одна частица не попала,  — тёмной.

При анализе результатов эксперимента рассматривают изолированные точки.

Точка называется изолированной, если эта точка светлая (независимо от того, сколько частиц в неё попало), а другие светлые точки в том же ряду либо отсутствуют, либо находятся на расстоянии более 1000.

Вам необходимо по заданному протоколу определить наибольшее количество изолированных точек, расположенных в одном ряду, и номер ряда, в котором это количество встречается. Если таких рядов несколько, укажите максимально возможный номер.

Задание 26

Входные данные.

Первая строка входного файла содержит целое число N  — общее количество частиц, попавших на экран. Каждая из следующих N строк содержит 2 целых числа: номер ряда и номер позиции в ряду.

В ответе запишите два целых числа: сначала максимальное количество изолированных точек в одном ряду, затем  — номер ряда, в котором это количество встречается.

Ответ:

Решение.

Это задание ещё не решено, приводим решение прототипа.

Точка экрана, в которую попала хотя бы одна частица, считается светлой, точка, в которую ни одна частица не попала,  — тёмной.

При анализе результатов эксперимента рассматривают изолированные точки.

Задание 26

Входные данные.

Ответ:

Приведём решение на языке 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])

№ п/п	№ задания	Ответ
1	75290	17 99418

Ключ