Задача к ЕГЭ по информатике на тему «задачи под вебы» №1

Задача с сайта https://kpolyakov.spb.ru/

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

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

Входные данные представлены в файле 26-73.txt следующим образом. В первой строке входного файла записано целое число $N$ – количество частиц, попавших на экран. В каждой из следующих $N$ строк записаны по два числа, разделённые пробелом: номер строки и номер позиции в строке.

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

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

1 2

2 3

3 6

2 4

1 3

2 5

2 4

При таких исходных данных имеется три цепочки светлых точек: в позициях 2 и 3 строки 1, в позициях 4, 5 и 6 строки 2 (это самая длинная цепочка!) и точка в позиции 6 строки 3. Ответ: 3 2.

Решение в Excel (способ 1):

Открываем файл в $Excel$ $→$ Данные $→$ Текст по столбцам с разделителями – точка с запятой.

Переносим значение из первой строки вправо и удаляем пустую строку.

Сортируем сначала по столбцу $A$ , потом по столбцу $B$ .

В столбце $C$ посчитаем длины цепочек. В ячейке $C1$ запишем значение 1. В ячейке $C2$ напишем формулу

= ЕС ЛИ (И (A2 = A1; B2 − B1 = 1);C1 + 1;ЕСЛ И(И(A2 = A1;B2 = B1 );C1; 1))

и растянем до конца столбца.

Переходим в Данные $→$ Фильтр, в столбце $C$ выбираем максимальную длину цепочки – 8. Максимальный номер подходящей строки – 338.

Решение в Excel (способ 2):

Сортируем данные сначала по столбцу $A$ , потом по столбцу $B$ .

Удалим повторяющиеся значения: «Данные» $→$ «Удалить дубликаты».

В столбце $C$ посчитаем длины цепочек. В ячейке $C1$ запишем значение 1. В ячейке $C2$ напишем формулу

= ЕС ЛИ(И (A2 = A1; B2 − B1 = 1);C1 + 1;1)

и растянем до конца столбца.

Решение в Python:

f=open(’26-73.txt’) # Открываем файл
n = int(f.readline()) # Kоличество заявок
# tuple создает кортеж (неизменяемый список)
# ’a’ - список уникальных кортежей
# Получаем сортированные координаты частиц
a = sorted(set(tuple(map(int, i.split())) for i in f))

l = 0 # Текущая длина цепочки
lmax = 0 # Максимальная длина цепочки
s = 0 # Номер строки с максимальной цепочкой
for i in range(len(a)-1): # Рассматриваем все пары
# Если номера строк совпадают и позиции идут подряд
    if (a[i][0] == a[i+1][0]) and (a[i+1][1]-a[i][1] == 1):
        l += 1 # Увеличиваем длину цепочки
# Если текущая цепочка не меньше максимальной
        if l >= lmax:
            lmax = l # Обновляем максимальную длину строки
            s = a[i][0] # Обновляем номер строки
    else:
        l = 0 # Иначе обнуляем длину текущей строки
print(lmax + 1, s) # Максимальная длина цепочки и номер ряда

Ответ: 8 338