Разбор задания № 26 ЕГЭ по информатике

Разбор решение задания № 26 ЕГЭ по информатике будет полезно учащимся 11 классов при подготовке к экзамену.

В работе приводится алгоритм решения задания 26 ЕГЭ, а также листинг программы на языке Python.

Условие задания

Организация купила для своих сотрудников все места в нескольких подряд идущих рядах на концертной площадке. Известно, какие места уже распределены между сотрудниками.

Найдите ряд с наибольшим номером, в котором есть два соседних места, таких что слева и справа от них в том же ряду места уже распределены (заняты).

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

Что нужно знать для успешного выполнения задания № 26 к ЕГЭ

• Считывание данных из файла в список.
• Работа со списком. (вложенным списком)
• ортировку данных по возрастанию и убыванию значений.
• Основы программирования.

Входные данные задания 26 ЕГЭ

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

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

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

Пример входных данных к заданию 26 ЕГЭ по информатике

Для данного примера ответом будет являться пара чисел 60 и 23.

Решение

Согласно условию задачи нам следует найти самый большой номер ряда, в котором найдется 2 соседних незанятых места, что слева и справа от них будут 2 занятых места, что соответствует схеме занято - свободно - свободно - занято.

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

Алгоритм решения задачи

Читаем данные из файла в список списков. В результате у нас будет список, каждый элемент которого будет являться списком из 2-х чисел. Поменяем знак второго элемента в каждом вложенном списке на противоположный.

Сделаем сортировку списка с помощью sort(). Т. к. на предыдущем шаге мы поменяли знак второго элемента на противоположный, то минимум станет максимумом. Это облегчит решение, т.к. теперь нужно будет искать максимальный ряд и максимальное место.

Идем по внешнему списку и проверяем: если ряд совпал и разность по местам равна 3, что соответствует вышеописанной схеме "занято" - "свободно" - "свободно" - "занято", сохраняем ряд и восстанавливаем место (берем со знаком минус и добавляем 1, т.к. нужно получить минимальный номер свободного места).

Программа на языке Python

f = open('test.txt', 'r') # открываем текстовый файл для чтения
count = int(f.readline()) # считывает количество строк в файле
nums = []

for i in range(count): # цикл for будет выполняться столько раз, сколько строк в файле
   busy = list(map(int, f.readline().split()))
   busy[1] = -busy[1] # меняем знак второго элемента на противоположный
   nums += [busy] # делаем список списков

nums.sort() # сортируем список

print(nums) # вывод на экран данных
row, place = 0, 0 # инициализация ряда и места

for i in range(1, len(nums)): # идем по списку
   if nums[i][0] == nums[i - 1][0] and nums[i][1] - nums[i - 1][1] == 3: # если ряд совпал и разность по местам равна 3
   row = nums[i][0] # сохраняем ряд
   place = - nums[i][1] + 1 # сохраняем первое свободное место с наименьшим номером

print(row, place) # печать результатов на экране