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

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

Организация купила для своих сотрудников все места в нескольких рядах на стадионе. Известно, какие места уже распределены между сотрудниками. Найдите ряд с наименьшим номером, в котором есть четыре соседних места, таких что слева и справа от них в том же ряду места уже распределены (заняты). Гарантируется, что есть хотя бы один ряд, удовлетворяющий условию. По заданной информации определите минимальный номер ряда, удовлетворяющего условию, и наибольший номер места из найденных в этом ряду четверок мест.

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

В первой строке входного файла находится одно число: $N$ — количество занятых мест (натуральное число, не превышающее $10000$ ). В следующих $N$ строках находятся пары чисел: ряд и место выкупленного билета (числа не превышают $100$ $000$ ).

Пример входных данных:

$7$

$4 1$

$3 5$

$4 6$

$4 7$

$3 6$

$3 10$

$5 8$

При таких исходных данных ответ должен содержать $2$ числа: $3$ — минимальный номер ряда, и $9$ — наибольший номер места из выбранной четверки в $3$ ряду (была выбрана четверка с номерами $6,7,8,9$ ).

Решение 1 (Excel/LibreOffice)
Откроем текстовый документ. Запомним первое число и удалим его. Скопируем все числа в Excel или LibreOffice. В разделе Главная $⇒$ Сортировка и фильтр $⇒$ Настраиваемая сортировка делаем сортировку столбцов:

В ячейке $C2$ записываем формулу:

=ЕСЛИ(И(A2=A1;B2=B1+5);»НАШЁЛ»;0),

В ячейке $C3$ записываем формулу:

=ЕСЛИ(И(A3=A2;ИЛИ(B3=B2+5;B3=B1+5));»НАШЁЛ»;0),

В ячейке $C4$ записываем формулу:

=ЕСЛИ(И(A4=A3;ИЛИ(B4=B3+5;B4=B2+5;B4=B1+5));»НАШЁЛ»;0),

В ячейке $C5$ записываем формулу:

=ЕСЛИ(И(A5=A4;ИЛИ(B5=B4+5;B5=B3+5;B5=B2+5;B5=B1+5));»НАШЁЛ»;0),

В ячейке $C6$ записываем формулу:

=ЕСЛИ(И(A6=A5;ИЛИ(B6=B5+5;B6=B4+5;B6=B3+5;B6=B2+5;B6=B1+5));»НАШЁЛ»;0)

и растягиваем её на диапазон $[C6 : C10000]$ . Наводим курсор на столбец $C$ , нажимаем на Главная $⇒$ Сортировка и фильтр $⇒$ Фильтр. Сортируем столбец $C$ по критерию «НАШЁЛ». Видим, что наименьший номер ряда — $2$ , а наибольшее место — $74$ .

Решение 2 (Python)

f = open(’Задание_26__mixo__t7qt.txt’)
n = int(f.readline())
max_row = 0 # максимальный ряд в файле
max_seat = 0 # максимальное место в ряду в файле
for i in range(n):
    x, y = map(int, f.readline().split()) # считываем текущую строку
    max_row = max(max_row, x)
    max_seat = max(max_seat, y)
a = [] # матрица занятых и пустых мест
for i in range(max_row+1): # проход до значения максимального ряда в файле
    a.append([0]*(max_seat+1)) # добавление мест
f.close()
f = open(’Задание_26__mixo__t7qt.txt’)
n = int(f.readline())
for i in range(n):
    x, y = map(int, f.readline().split())
    a[x][y] = 1 # отмечаем, что место - занято
maxim = 0
for i in range(max_row+1): # проход по рядам
    for j in reversed(range(max_seat)): # проход по местам ряда
        if a[i][j] == 1 and a[i][j-5] == 1:
            maxim = j - 1
            break
    if maxim != 0:
        print(i, maxim)
        break

Ответ: 2 74