Задача к ЕГЭ по информатике на тему «Поиск мест на поле (билеты, саженцы, матрицы)» №1

Задание выполняется с использованием прилагаемых файлов

При проведении эксперимента заряженные частицы попадают на чувствительный экран, представляющий из себя матрицу размером $10000$ на $10000$ точек. При попадании каждой частицы на экран в протоколе фиксируются координаты попадания: номер ряда (целое число от $1$ до $10000$ ) и номер позиции в ряду (целое число от $1$ до $10000$ ). Точка экрана, в которую попала хотя бы одна частица, считается светлой, точка, в которую ни одна частица не попала, — тёмной. При анализе результатов эксперимента рассматривают группы светлых точек, расположенных в одном ряду подряд, то есть без тёмных точек между ними. Вам необходимо по заданному протоколу определить максимальную длину такой группы и номер ряда, в котором эта группа встречается. Если таких рядов несколько, укажите минимально возможный номер.

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

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

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

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

Пример входного файла:

$7$

$1 2$

$2 3$

$3 6$

$2 4$

$1 3$

$2 5$

$2 4$

При таких исходных данных имеется три группы светлых точек: в позициях $2− 3$ ряда $1$ , в позициях $3 − 5$ ряда $2$ и в позиции $6$ ряда $3$ . Самая длинная группа длины $3$ находится во $2$ ряду. Ответ: $3 2$ .

Решение 1 (Excel/LibreOffice)
Откроем текстовый документ, скопируем значения и перенесем их в Excel или LibreOffice.
Воспользуемся настраиваемой сортировкой, на первый уровень расположим столбец $A$ (по возрастанию), на второй — столбец $B$ (по возрастанию). Выделим полностью столбцы A и B , перейдём в раздел «Данные»и нажимаем на инструмент «Удалить дубликаты в появившемся окне выбираем «Выделить все»и нажимаем «ОК»(это удалит частицы, которые были по ошибке сняты дважды). В ячейку $C1$ запишем $1$ , а в $C2$ — формулу =ЕСЛИ(И(A2=A1;B2-B1=1);C1+1;1), скопируем её на все свободные клеточки этого столбца. Находим максимальную длину группы точек в столбце $C$ и номер ряда, в котором эта группа встречается. Выписываем этот номер и наименьший номер ряда, где нашлись обозначенные в задаче точки.

Решение 2 (Python)

f = open(’26__1r21f.txt’)
n = int(f.readline())
a = [[0] * 10001 for j in range(10001)] # матрица, в которой 1 будут указаны занятые пиксели, 0 - свободные пиксели
maxim = 0
row = 0
for i in range(n):
    x, y = [int(s) for s in f.readline().split()]
    a[x][y] = 1 # отмечаем, что данный пиксель занят
for i in range(10001):
    counter = 0 # счетчик подряд идущих занятых пикселей
    for j in range(10001):
        if a[i][j] == 1:
            counter += 1
        else:
            counter = 0
        if counter > maxim: # если счётчик больше максимума
            maxim = counter # перезаписываем максимум
            row = i # записываем ряд
print(maxim, row)

Ответ: 10 2786