26. Прикладная задача: Необходимо купить два билета на такие соседние места в одном ряду, чтобы…
При онлайн-покупке билета на концерт известно, какие места в зале уже заняты. Необходимо купить два билета на такие соседние места в одном ряду, чтобы перед ними все кресла с такими же номерами были свободны, а ряд находился как можно дальше от сцены. Если в этом ряду таких пар мест несколько, найдите пару с наименьшими номерами. В ответе запишите два целых числа: искомый номер ряда и наименьший номер места в найденной паре. Нумерация рядов и мест ведётся с $1$. Гарантируется, что хотя бы одна такая пара в зале есть.
Условие «перед ними все кресла с такими же номерами свободны» устроено жёстче, чем в похожей задаче про одно место: там достаточно было свободного участка, а здесь свободными должны быть все ряды от первого. Значит для каждого номера места важна ровно одна величина — номер первого ряда, где это место занято. Обозначим её $first[p]$; если место $p$ не занято нигде, считаем $first[p] = M+1$.
Тогда пара мест $p$ и $p+1$ годится в ряду $r$ при условии $r < first[p]$ и $r < first[p+1]$, то есть $r \le \min(first[p], first[p+1]) - 1$. Обратите внимание, что сюда автоматически входит и требование «сами эти два кресла свободны»: если бы место $p$ было занято в самом ряду $r$, то $first[p] \le r$.
Дальше просто перебираем все пары соседних номеров мест и берём максимум этой величины. Ряд нужен как можно дальше от сцены, то есть с наибольшим номером; при совпадении берём наименьший номер места, что достигается перебором $p$ по возрастанию со строгим сравнением.
Перебирать сами кресла нельзя — их до десяти миллиардов. Массив $first$ имеет размер $K$, и этого достаточно.
f = open('26-16.txt')
N, M, K = map(int, f.readline().split())
first = [M+1] * (K+2) # первый ряд, где место p занято
for _ in range(N):
r, p = map(int, f.readline().split())
if r < first[p]:
first[p] = r
best_row, best_seat = 0, None
for p in range(1, K): # пара соседних мест p и p+1
r = min(first[p], first[p+1]) - 1
if r > best_row:
best_row, best_seat = r, p
print(best_row, best_seat) # 21028 6660
Проверка. В файле $N = 9992$, $M = 99906$, $K = 6661$. Место $6660$ не занято ни в одном ряду, а место $6661$ впервые занято в ряду $21029$. Значит пара работает вплоть до ряда $21028$, и оба кресла в нём свободны. Другой пары с таким же номером ряда нет, так что выбор наименьшего номера места не понадобился. На типовом примере из условия программа выдаёт $5$ и $6$.