Задача

3/11

_St-23_02-ege-26(a)

Теория

#z26 Статград декабрь 2022 года
def lines(A,m): # вычисления числа линий с строке, заданной множеством точек
    # m - миниальное число точек, принимаемое за линию
    B=list(A) # перевод в список
    B.sort()  # сортировка списка
    B.append(-1) # добавление барьера - гарантия обработки последней линии
    n=0  # кол-во линий в строке
    j=1 # длина текущей линии
    for i in range(1,len(B)): # пробег с 2-го места (1-е учли в j=1)
        if B[i]-B[i-1]==1: j+=1 # линия продолжается
        else : # линия закончилась, обработка
            if j>=m : n+=1 # фиксация линии требуемой длины
            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,3) # вычисление числа линий в строке
        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).
Точка экрана, в которую попала хотя бы одна частица, считается светлой, точка, в которую ни одна частица не попала, – тёмной.
При анализе результатов эксперимента рассматривают линии. Линией называют группу светлых точек, расположенных в одном ряду подряд, то есть без тёмных точек между ними. Линия должна содержать не менее 3 светлых точек, слева и справа от линии должна быть тёмная точка или край экрана.
Вам необходимо по заданному протоколу определить наибольшее количество линий, расположенных в одном ряду, и номер ряда, в котором это количество встречается. Если таких рядов несколько, укажите максимально возможный номер.
Входные данные
Первая строка входного файла содержит целое число N – общее количество частиц, попавших на экран.
Каждая из следующих N строк содержит 2 целых числа: номер ряда и номер позиции в ряду.

 

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

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

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