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

Задания

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

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

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

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

Задание 26

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

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

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

Ответ:

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

№ п/п	№ задания	Ответ
1	55613	26 97586

Ключ