Карточки
Тесты
Главная
Курсы
Подписка
26. Прикладная задача: #298096
Организация купила для своих сотрудников все места в нескольких подряд идущих рядах на концертной площадке. Известно, какие места уже распределены между сотрудниками. Найдите ряд с наибольшим номером, в котором есть два соседних места, таких что слева и справа от них в том же ряду места уже распределены (заняты). Гарантируется, что есть хотя бы один ряд, удовлетворяющий этому условию. В ответе запишите два целых числа: номер ряда и наименьший номер места из найденных в этом ряду подходящих пар свободных мест.
Место свободно, если его нет в списке занятых. Нужна пара соседних свободных мест, окружённая занятыми — то есть занятые места $a$ и $b$ в одном ряду, между которыми ровно два свободных. Это в точности условие $b — a = 3$.
Значит группируем занятые места по рядам, каждый ряд сортируем и смотрим только на соседние элементы отсортированного списка: если разница равна $3$, найдена подходящая пара, её меньший номер равен $a+1$. Перебирать все места ряда не нужно — их номера доходят до $100000$, а занятых всего $10000$.
Дальше по условию: сначала выбираем ряд с наибольшим номером среди тех, где такая пара нашлась, и уже внутри него берём наименьший номер места.
from collections import defaultdict
f = open('26-29.txt')
n = int(f.readline())
rows = defaultdict(list)
for _ in range(n):
r, p = map(int, f.readline().split())
rows[r].append(p)
best_row, best_seat = -1, None
for r, seats in rows.items():
seats = sorted(set(seats))
# разница 3 между занятыми = ровно два свободных места между ними
pairs = [seats[i] + 1 for i in range(len(seats) - 1) if seats[i+1] - seats[i] == 3]
if pairs and r > best_row:
best_row, best_seat = r, min(pairs)
print(best_row, best_seat) # 79936 78782
Проверка. Занятых мест $9986$, подходящих рядов $996$, максимальный по номеру из них — $79936$. В нём нашлись три подходящие пары, начинающиеся с мест $78782$, $85874$ и $86480$; наименьшая идёт в ответ. Наибольший номер ряда в файле вообще — $99998$, но подходящей пары в нём нет, поэтому брать его нельзя.
20
