При онлайн-покупке билета на концерт известно, какие места в зале уже заняты. Необходимо купить билет на такое место в ряду, чтобы перед ним как можно больше идущих подряд кресел с таким же номером было свободно. Если места, удовлетворяющие этому условию, есть в нескольких рядах, то нужно выбрать ряд, расположенный как можно ближе к сцене. В ответе запишите два целых числа: искомый номер ряда и количество свободных кресел перед выбранным местом. Нумерация рядов и мест ведётся
Входные данные.
В первой строке входного файла находятся три числа: N — количество занятых мест в зале (целое положительное число, не превышающее 10 000), М — количество рядов (целое положительное число, не превышающее 100 000) и K — количество мест в каждом ряду (целое положительное число, не превышающее 100 000). В следующих
Выходные данные.
Два целых положительных числа: искомый номер ряда и количество свободных кресел перед выбранным местом.
Ответ:
Приведём решение на языке Python.
File = open("pr1.txt")
N, M, K = map(int, File.readline().split())
places = []
for i in range(N):
row, place = map(int, File.readline().split())
places.append([place, row])
places.sort()
maxCount = 0
minRow = 0
for p in range(1, N):
previousPlace = places[p - 1][0]
previousRow = places[p - 1][1]
currentPlace = places[p][0]
currentRow = places[p][1]
if currentPlace == previousPlace:
count = (currentRow - 1) - (previousRow + 1)
if maxCount < count:
maxCount = count
minRow = currentRow - 1
elif maxCount == count:
minRow = min(minRow, currentRow - 1)
elif currentPlace - previousPlace == 1:
count = M - (previousRow + 1)
if maxCount < count:
maxCount = count
minRow = M
elif maxCount == count:
minRow = min(minRow, M)
count = currentRow - 2
if maxCount < count:
maxCount = count
minRow = currentRow - 1
elif maxCount == count:
minRow = min(minRow, currentRow - 1)
else:
maxCount = K - 1
minRow = M
break
print(minRow, maxCount)
Ответ: 665 61.
Приведём другое решение на языке Python.
data = open('2626.txt').read().strip().split('\n')
n, m, k = map(int, data.pop(0).split())
occupied_places = [[0, m + 1] for i in range(k)]
for row in data:
row_m, row_k = map(int, row.split())
occupied_places[row_k - 1].append(row_m)
occupied_places = [sorted(places) for places in occupied_places]
distances = []
for i, values in enumerate(occupied_places):
for place_index in range(len(values) - 1):
current_place = values[place_index]
next_place = values[place_index + 1]
distance = next_place - current_place - 2
if distance >= 0:
distances.append([next_place - 1, distance])
distances.sort(key=lambda x: (-x[1], x[0]))
print(distances[0])
Приведём решение Юрия Красильникова на языке Python.
f=open('2626.txt')
n,m,k=map(int, f.readline().split())
a=sorted([list(map(int,s.split())) for s in f],key=lambda x: x[::-1])
maxpust=max([a[i][0]-a[i-1][0] for i in range(1,len(a)) if a[i][1] == a[i-1][1]])
rows=[a[i][0]-1 for i in range(1,len(a)) if a[i][0]-a[i-1][0]==maxpust and a[i][1]==a[i-1][1]]
print(min(rows),maxpust-2)