OpenFIPI 2.0

26

6

AD6F70

undefined Задание выполняется с использованием прилагаемых файлов.

При онлайн-покупке билета на концерт известно, какие места в зале уже заняты. Необходимо купить два билета на такие соседние места в одном ряду, чтобы перед ними все кресла с такими же номерами были свободны, а ряд находился как можно дальше от сцены. Если в этом ряду таких пар мест несколько, найдите пару с наименьшими номерами. В ответе запишите два целых числа: искомый номер ряда и наименьший номер места в найденной паре. Нумерация рядов и мест ведётся с 1. Гарантируется, что хотя бы одна такая пара в зале есть.

 

Входные данные

В первой строке входного файла находятся три числа: N – количество занятых мест в зале (целое положительное число,
не превышающее 10 000), M – количество рядов (целое положительное число, не превышающее 100 000) и K – количество мест в каждом ряду (целое положительное число, не превышающее 100 000). В следующих N строках находятся пары натуральных чисел: номер ряда и номер места занятого кресла соответственно (первое число не превышает значения M, а второе – K).

Выходные данные

Два целых положительных числа: наибольший номер ряда и наименьший номер места в найденной паре кресел.

 

Типовой пример организации данных во входном файле

7 7 8

1 1

6 6

5 5

6 7

4 4

2 2

3 3

При таких исходных данных ответом является пара чисел 5 и 6. Условию задачи удовлетворяют места 6 и 7 в ряду 5: перед креслами 6 и 7 нет занятых мест и это первая из двух возможных пар в этом ряду. В рядах 6 и 7 искомую пару найти нельзя.

 

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

 

21028 6660

f = open('301_26.txt')
n, m, k = map(int, f.readline().split())
a = [[int(i) for i in line.split()] for line in f.read().strip().split('\n')]
d = dict()
for row, col in a:
    if col not in d or row < d[col]:
        d[col] = row
mx_row = 0
for col in range(1, k):
    mx = min(d.get(col, m + 1) - 1, d.get(col + 1, m + 1) - 1)
    if mx > mx_row:
        mx_row = mx
        c = col
print(mx, c)
f.close()

Просмотреть отправленные ответы AD6F70