При онлайн-покупке билета на концерт известно, какие места в зале уже заняты. Необходимо купить два билета на такие соседние места в одном ряду, чтобы перед ними все кресла с такими же номерами были свободны, а ряд находился как можно дальше от сцены. Если в этом ряду таких пар мест несколько, найдите пару с наибольшими номерами. В ответе запишите два целых числа: искомый номер ряда и наибольший номер места в найденной паре. Нумерация рядов и мест ведётся
Входные данные.
В первой строке входного файла находятся три числа: N — количество занятых мест в зале (целое положительное число, не превышающее 10 000), М — количество рядов (целое положительное число, не превышающее 100 000) и К — количество мест в каждом ряду (целое положительное число, не превышающее 100 000). В следующих
Выходные данные.
Два целых положительных числа: наибольший номер ряда и наибольший номер места в найденной паре кресел.
Типовой пример организации данных во входном файле:
7 7 8
1 1
6 6
5 5
6 7
4 4
2 2
3 3
При таких исходных данных ответом является пара
Ответ:
Приведём решение на языке Python.
f = open('69934.txt')
N, M, K = [int(x) for x in f.readline().split()]
mini = [M+1]*(K+1)
for i in range(N):
rad, mesto = [int(x) for x in f.readline().split()]
mini[mesto] = min(mini[mesto], rad)
Nrad = 0
Nmesto = []
for i in range(1, K):
Nrad = max(Nrad, min(mini[i]-1, mini[i+1]-1))
if min(mini[i]-1, mini[i+1]-1) == Nrad:
Nmesto.append(i+1)
print(Nrad, max(Nmesto))
Ответ: 99999 4989.
Приведём решение Юрия Красильникова на языке Python.
f = open('69934.txt')
n,m,k = map(int, f.readline().split())
sbr = [m+1]*k
for s in f:
r,p = map(int, s.split())
sbr[p-1] = min(sbr[p-1], r)
pairs = [min(sbr[i-1], sbr[i]) for i in range(1, len(sbr))]
mr = max(pairs)
print(mr - 1, max(i for i in range(len(pairs)) if pairs[i] == mr) + 2)