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

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

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

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

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

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

Решение (Excel/LibreOffice)

Сначала перенесем данные из файла в Excel, скопировав и вставив с разделителем пробел, а также удалим первую строчку.

Настраиваемой сортировкой отсортируем в первую очередь по столбцу $A$ по возрастанию, во вторую — по столбцу $B$ по возрастанию.

Выделим полностью столбцы $A$ и $B$ , перейдём в раздел Данные и нажимаем на инструмент Удалить дубликаты, в появившемся окне выбираем Выделить все и нажимаем ОК (это удалит деревья, которые были по ошибке сняты дважды).

В LibreOffice Calc необходимо также выделить оба столбца, применить фильтр и перейти в раздел Фильтр по условию -> Стандартный фильтр.

В условиях фильтра необходимо через И выбрать столбцы $A$ и $B$ , установить значение Не пусто и поставить галочку напротив Без повторений. После чего нужно скопировать отфильтрованные значения на новый лист и работать уже там.

Чтобы определить самую длинную линию, в ячейку $C1$ запиешем ”нет”, а в ячейку $C2$ запишем и растянем до конца таблицы следующую формулу:

=ЕСЛИ(A2=A1;C1;ЕСЛИ(B2=1;”да”;”нет”))

Таким образом ”да” проставится для рядов, начинающихся со светлой точки. В ячейку $D1$ запишем 1, а в ячейку $D2$ запишем и растянем до конца таблицы следующую формулу:

=ЕСЛИ(A2=A1;D1+1;1)

С её помощью мы посчитаем количество точек в каждом ряду. В ячейку $E1$ запишем и растянем до конца таблицы следующую формулу:

=ЕСЛИ(И(A1<>A2;C1=”да”;B1=10000);1;0)

С помощью неё мы отделим ряды, и начавшиеся и кончившиеся светлой точкой.

Отфильтруем данные по столбцу $C$ , убрав все нули, и получим ряды, для которых выполнилось условие. Значения из столбцов $D$ и $A$ запишем в ответ.

Решение (Python)

f = open(’m7_26_18_04__3u8yv.txt’)

n = int(f.readline())

tr = [list(map(int, i.split())) for i in f]
tr.sort()

new_tr = [[0] * 10_001 for i in range(10_001)] # матрица свободных и занятых мест
for x, y in tr:
    new_tr[x][y] = 1 # отмечаем, что место - занято

max_count = 1
row = 0

for i in range(len(new_tr)):
    # если первое и последнее место в ряду - заняты и при этом в ряду максимальное количество светлых точек
    if new_tr[i][1] == new_tr[i][-1] == 1 and sum(new_tr[i]) > max_count:
        max_count = sum(new_tr[i])
        row = i
print(max_count, row)

Ответ: 13 9298