Question

При онлайн-⁠покупке билета на концерт известно, какие места в зале уже заняты. Необходимо купить два билета на такие соседние места в одном ряду, чтобы перед ними все кресла с такими же номерами были свободны, а ряд находился как можно дальше от сцены. Если в этом ряду таких пар мест несколько, найдите пару с наибольшими номерами. В ответе запишите два целых числа: искомый номер ряда и наибольший номер места в найденной паре. Нумерация рядов и мест ведётся с 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 искомую пару найти нельзя.

Ответ:

Accepted Answer

Answer

### СТАТЕМЕНТ

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

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

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

**Пример входных данных:**
```
7 7 8
1 1
6 6
5 5
6 7
4 2
2 3
3 3
```

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

### РЕШЕНИЕ

Идея решения: для каждого номера места найти минимальный номер ряда, в котором оно занято; затем для каждой пары соседних мест определить, до какого ряда они свободны, и выбрать пару с максимальным номером ряда, а при равенстве — с максимальным номером места.

Для каждого места $i$ (от 1 до $K$) вычислим минимальный номер ряда, в котором оно занято. Если место не занято ни в одном ряду, присвоим ему значение $M + 1$.

Затем для каждой пары соседних мест $(i, i+1)$ найдём, до какого ряда они оба свободны. Это значение равно $\min(	ext{mini}[i], 	ext{mini}[i+1]) - 1$, где $	ext{mini}[j]$ — минимальный номер ряда, в котором занято место $j$.

Выберем пару с максимальным номером ряда. Если таких пар несколько, возьмём ту, у которой больший номер места (второе место в паре).

```python
f = open('69934.txt')
n, m, k = map(int, f.readline().split())

mini = [m + 1] * k
for _ in range(n):
    r, p = map(int, f.readline().split())
    mini[p - 1] = min(mini[p - 1], r)

pairs = [min(mini[i - 1], mini[i]) for i in range(1, len(mini))]
max_row = max(pairs)

best_place = max(
    i for i in range(len(pairs)) if pairs[i] == max_row
) + 2

print(max_row - 1, best_place)
```

Сложность: $O(N + K)$ — один проход по занятым местам и один проход по всем местам в зале.

### ОТВЕТ

Задание №26ПрограммированиеЕГЭ по информатике