При онлайн-покупке билета на концерт известно, какие места в зале уже
Условие
При онлайн-покупке билета на концерт известно, какие места в зале уже заняты. Необходимо купить два билета на такие соседние места в одном ряду, чтобы перед ними все кресла с такими же номерами были свободны, а ряд находился как можно дальше от сцены. Если в этом ряду таких пар мест несколько, найдите пару с наибольшими номерами. В ответе запишите два целых числа: искомый номер ряда и наибольший номер места в найденной паре. Нумерация рядов и мест ведётся с 1. Гарантируется, что хотя бы одна такая пара в зале есть.
Задание 26Входные данные.В первой строке входного файла находятся три числа: N — количество занятых мест в зале (целое положительное число, не превышающее 10 000), М — количество рядов (целое положительное число, не превышающее 100 000) и К — количество мест в каждом ряду (целое положительное число, не превышающее 100 000). В следующих N строках находятся пары натуральных чисел: номер ряда и номер места занятого кресла соответственно (первое число не превышает значения М, а второе — K).Выходные данные.
Два целых положительных числа: наибольший номер ряда и наибольший номер места в найденной паре кресел. Типовой пример организации данных во входном файле:7 7 81 16 65 56 74 42 23 3При таких исходных данных ответом является пара чисел 5 и 8. Условию задачи удовлетворяют места 7 и 8 в ряду 5: перед креслами 7 и 8 нет занятых мест и это последняя из двух возможных пар в этом ряду. В рядах 6 и 7 искомую пару найти нельзя. Ответ:
Ответ
Ответ и полный разбор откроются после входа
Посмотреть ответРешение по шагам
Как рассуждать
Решение. Приведём решение на языке 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 = 0Nmesto = []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))
Осталось ещё 1 шаг
Приведём решение Юрия Красильникова на языке…
Бесплатно · займёт минуту