При онлайн-покупке билета на концерт известно, какие места в зале уже заняты. Необходимо купить два билета на такие соседние места в одном ряду, чтобы перед ними было занято не более двух кресел с такими же номерами, а ряд находился как можно дальше от сцены. Сцена расположена перед первым рядом. Если в этом ряду таких пар мест несколько, найдите пару с наибольшими номерами мест. Нумерация рядов и мест ведётся с 1. Гарантируется, что хотя бы одна такая пара в зале есть. Определите наибольший номер ряда и наибольший номер места для найденной пары мест.
Входные данные представлены в файле следующим образом. В первой строке входного файла находятся три числа: 
– количество занятых мест в зале (целое положительное число, не превышающее 10000), 
– количество рядов (целое положительное число, не превышающее 100 000) и 
– количество, мест в каждом ряду (целое положительное число, не превышающее 100 000). В следующих 
строках находятся пары натуральных чисел: номер ряда и номер места занятого кресла соответственно (первое число не превышает значения 
, а второе – 
).
Запишите в ответе два целых числа: искомый номер ряда и наибольший номер места в найденной паре.
Пример входного файла:
8 7 4
1 1
4 1
3 2
1 3
2 3
6 3
5 4
7 2
Условию задачи удовлетворяют места 1 и 2 в ряду 6: перед 1 креслом 2 занятых места, а перед 2 местом 1 занятое место.
Решение 1
f = open("2.txt")
n, m, k = map(int, f.readline().split())
row = [[m+1] for i in range(k)]
for i in range(n):
x, y = map(int, f.readline().split())
row[y-1].append(x)
# дублируем массив a удаляя из него до 2х занятых мест минимальных рядов
b = []
for i in range(k):
b.append(sorted(row[i]))
if len(b[i]) >= 4:
b[i].pop(2)
b[i].pop(1)
elif len(b[i]) == 3:
b[i].pop(1)
mx_r = 0# максимальный ряд
mx_i = 0 # максимальное место
for i in range(1, len(b) - 1):
# из двух (вертикальных) соседних рядов берем макс место
# (номер горизонтального ряда - mx_r), перед ним все будут свободны;
# соответствеенно, чем он больше, тем дальше от сцене
if max(b[i + 1] + b[i]) >= mx_r:
x = max(b[i + 1] + b[i])
while x in row[i] or x in row[i + 1]:
x -= 1
mx_r = x
mx_i = i
print(mx_r, mx_i+2)
Решение 2
f = open("26.txt")
n, m, k = map(int, f.readline().split())
a = [[0, m + 1] for i in range(k)]
for i in f:
x, y = map(int, i.split())
a[y-1].append(x)
# дублируем массив a удаляя из него до 2х занятых мест минимальных рядов
b = []
for i in range(k):
b.append(sorted(a[i]))
if len(b[i]) >= 4:
b[i].pop(2)
b[i].pop(1)
elif len(b[i]) == 3:
b[i].pop(1)
mx = 0
mx_i = 0 # минимальное место
for i in range(k - 1):
# print(i, sorted(a[i]))
t1 = sorted(b[i])
t2 = sorted(b[i + 1])
spot1 = t1[1] - t1[0] - 1 # выясняем сколько пустых мест перед текущим
spot2 = t2[1] - t2[0] - 1 # и перед соседним
# так как мы ранее удалили часть занятых мест, то нужно проверить, не заняты ли
# найденные места, если заняты, то спускаемся на ряд ниже, в нем гарантированно
# выполняются условия задачи
row = min(spot1, spot2)
while row in a[i] or row in a[i + 1]:
row -= 1
if row >= mx: # если найденный ряд выше чем нашлось ранее
mx = row # то обновляем максимум
mx_i = i # и сохраняем номер места
print(mx, mx_i + 2)