Дошкольникам
1 класс
2 класс
3 класс
4 класс
5 класс
6 класс
7 класс
8 класс
9 класс
10 класс
11 класс
ОГЭ
ЕГЭ
ВУЗ
Для всех
Назад

26. Прикладная задача: Необходимо купить два билета на такие соседние места в одном ряду, чтобы…

Задание #298064
Решено верно
Решено неверно
Сообщить о проблеме

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

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

В первой строке входного файла находятся три числа: $N$ – количество занятых мест в зале (целое положительное число, не превышающее $10000$), $M$ – количество рядов (целое положительное число, не превышающее $100000$) и $K$ – количество мест в каждом ряду (целое положительное число, не превышающее $100000$). В следующих $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$ искомую пару найти нельзя.

Условие «перед ними все кресла с такими же номерами свободны» устроено жёстче, чем в похожей задаче про одно место: там достаточно было свободного участка, а здесь свободными должны быть все ряды от первого. Значит для каждого номера места важна ровно одна величина — номер первого ряда, где это место занято. Обозначим её $first[p]$; если место $p$ не занято нигде, считаем $first[p] = M+1$.

Тогда пара мест $p$ и $p+1$ годится в ряду $r$ при условии $r < first[p]$ и $r < first[p+1]$, то есть $r \le \min(first[p], first[p+1]) - 1$. Обратите внимание, что сюда автоматически входит и требование «сами эти два кресла свободны»: если бы место $p$ было занято в самом ряду $r$, то $first[p] \le r$.

Дальше просто перебираем все пары соседних номеров мест и берём максимум этой величины. Ряд нужен как можно дальше от сцены, то есть с наибольшим номером; при совпадении берём наименьший номер места, что достигается перебором $p$ по возрастанию со строгим сравнением.

Перебирать сами кресла нельзя — их до десяти миллиардов. Массив $first$ имеет размер $K$, и этого достаточно.

f = open('26-16.txt')
N, M, K = map(int, f.readline().split())

first = [M+1] * (K+2)             # первый ряд, где место p занято
for _ in range(N):
    r, p = map(int, f.readline().split())
    if r < first[p]:
        first[p] = r

best_row, best_seat = 0, None
for p in range(1, K):             # пара соседних мест p и p+1
    r = min(first[p], first[p+1]) - 1
    if r > best_row:
        best_row, best_seat = r, p

print(best_row, best_seat)   # 21028 6660

Проверка. В файле $N = 9992$, $M = 99906$, $K = 6661$. Место $6660$ не занято ни в одном ряду, а место $6661$ впервые занято в ряду $21029$. Значит пара работает вплоть до ряда $21028$, и оба кресла в нём свободны. Другой пары с таким же номером ряда нет, так что выбор наименьшего номера места не понадобился. На типовом примере из условия программа выдаёт $5$ и $6$.

Показать
Очки опыта 20
Спросить Зави
0 заданий сегодня

Предложить улучшение