Задача

4/11

_St-23_03-ege-26(a)

Теория

#z26 Статград март 2023 года
def lines(A,m): # вычисления макс. длины линии с строке, заданной множеством точек
    # m - максимальное число идущих подря темных точек в линии
    B=list(A) # перевод в список
    B.sort()  # сортировка списка
    B.append(-m) # добавление барьера: -m гарантия обработки последней линии
    n=0  # максимальное кол-во точек в линии
    j=1 # длина текущей линии
    for i in range(1,len(B)): # пробег с 2-го места (1-е учли в j=1)
        d=B[i]-B[i-1] # возвожное увеличение в линии
        if d-1<=m: # d-1 = числу темных точек между B[i-1] и B[i]
            j+=d # линия продолжается
        else : # линия закончилась, обработка
            n=max(n,j) # фиксация максимальной длины линии
            j=1 # сброс длины линии
    B.clear() # очистка вспомогательного списка (необязательно)
    return n # возврат максимальной длины линий в строке

f=open('26.txt') # открытие файла
N=int(f.readline()) # чтение числа записей
print(N) # отладочная печать
DD=[] # список для координат точек
for _ in range(N): # чтение данных
    x,y=map(int,f.readline().split()) # координаты точки
    DD.append((x,y)) # добавление в список
DD.sort() # сортировка по номерам строк
DD.append((-1,-1)) # добавление барьера остановки
print('Ok') # отладочная печать (большой объём данных)
rezK,rezL=0,0 # результаты: макс. длина линии в строке, номер строки (макс.)
nr,y=DD[0] # 1-я точка : координаты
A=set() # множество для точек строки (точки могут совпадать) 
A.add(y) # заполнение стартовой точкой
for ii in range (1,len(DD)) : # получение точек одной строки
    x,y=DD[ii] # чтение координат очередной точки
    if x==nr : # проверка совпадения номеров строк
        A.add(y) # добавление точки в множество координат
    else: # формирование координат строки завершено
        k=lines(A,7) # вычисление макс. длины линии в строке
        if k>=rezK : # проверка и фиксация результата (учёт макс. номера ряда)
            rezK,rezL=k,nr 
        nr=x # изменение номера текущей строки
        A=set() # сброс множества координат
        A.add(y) # добавление 1-й точки
print(rezK,rezL) # вывод результатов
    
    
 

Задача

Задание выполняется с использованием прилагаемых файлов.
При проведении эксперимента заряженные частицы попадают на чувствительный экран, представляющий из себя матрицу размером 100 000 на 100 000 точек.
При попадании каждой частицы на экран в протоколе фиксируются координаты попадания: номер ряда (целое число от 1 до 100 000)
и номер позиции в ряду (целое число от 1 до 100 000).
Точка экрана, в которую попала хотя бы одна частица, считается светлой, точка, в которую ни одна частица не попала, – тёмной.
При анализе результатов эксперимента рассматривают линии. Линией называют группу точек, расположенных в одном ряду подряд.
Линия начинается и заканчивается светлыми точками, между которыми могут располагаться как светлые, так и тёмные точки, но не более семи тёмных точек подряд.
Вам необходимо по заданному протоколу определить наибольшее общее количество светлых и тёмных точек в одной линии и номер ряда,
в котором это количество встречается. Если таких рядов несколько, укажите максимально возможный номер.
Входные данные
Первая строка входного файла содержит целое число N – общее количество частиц, попавших на экран.
Каждая из следующих N строк содержит 2 целых числа: номер ряда и номер позиции в ряду.
В ответе, через пробел, запишите два целых числа:
сначала максимальное количество точек в одной линии, затем – номер ряда, в котором это количество встречается.

Выберите правильный ответ, либо введите его в поле ввода

Комментарий учителя