Е26.24 При онлайн-покупке билета на концерт известно, какие места в зале уже заняты

Администратор

2 года назад

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

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

TXT

наибольший номер ряда

наибольший номер места в найденной паре кресел

ЕГЭ по информатике Основная волна 07.06.2024 kompege.ru – задание №26

Показать решение...

Решение:

Решение на Python — Алексей Кабанов

f = open('26_17537.txt')
N, M, K = [int(x) for x in f.readline().split()]
min_ryad = [M+1]*(K+1)
for i in range(N):
    r, m = [int(x) for x in f.readline().split()]
    min_ryad[m] = min(min_ryad[m], r)
ans1 = 0
for i in range(1, K):
    ans1 = max(ans1, min(min_ryad[i]-1, min_ryad[i+1]-1))
ans2 = []
for i in range(1, K):
    if min(min_ryad[i]-1, min_ryad[i+1]-1)==ans1:
        ans2.append(i+1)
print(ans1, max(ans2))

f = open('26_17537.txt')

N, M, K = [int(x) for x in f.readline().split()]

min_ryad = [M+1]*(K+1)

for i in range(N):

r, m = [int(x) for x in f.readline().split()]

min_ryad[m] = min(min_ryad[m], r)

ans1 = 0

for i in range(1, K):

ans1 = max(ans1, min(min_ryad[i]-1, min_ryad[i+1]-1))

ans2 = []

for i in range(1, K):

if min(min_ryad[i]-1, min_ryad[i+1]-1)==ans1:

ans2.append(i+1)

print(ans1, max(ans2))

Объяснение кода:

Чтение входных данных:

Python

f = open('26_17537.txt') N, M, K = [int(x) for x in f.readline().split()]

1
2

f = open('26_17537.txt')
N, M, K = [int(x) for x in f.readline().split()]

Открываем файл '26_17537.txt' и читаем первую строку, содержащую три числа: N (количество занятых мест), M (количество рядов) и K (количество мест в каждом ряду).
Инициализация списка min_ryad:

Python

min_ryad = [M+1] * (K+1)

1

min_ryad = [M+1] * (K+1)

Создаем список min_ryad длиной K+1, инициализируя его значением M+1. Этот список будет хранить минимальные номера рядов для каждого места.
Заполнение списка min_ryad:

Python

for i in range(N): r, m = [int(x) for x in f.readline().split()] min_ryad[m] = min(min_ryad[m], r)

1
2
3

for i in range(N):
r, m = [int(x) for x in f.readline().split()]
min_ryad[m] = min(min_ryad[m], r)

Для каждого из N занятых мест читаем номер ряда r и номер места m. Обновляем значение в списке min_ryad для места m минимальным номером ряда.
Поиск максимального номера ряда:

Python

ans1 = 0 for i in range(1, K): ans1 = max(ans1, min(min_ryad[i] - 1, min_ryad[i + 1] - 1))

1
2
3

ans1 = 0
for i in range(1, K):
ans1 = max(ans1, min(min_ryad[i] - 1, min_ryad[i + 1] - 1))

Инициализируем переменную ans1 значением 0. Проходим по всем местам от 1 до K-1 и обновляем ans1 максимальным номером ряда, перед которым оба места i и i+1 свободны.
Поиск номеров мест:

Python

ans2 = [] for i in range(1, K): if min(min_ryad[i] - 1, min_ryad[i + 1] - 1) == ans1: ans2.append(i + 1)

1
2
3
4

ans2 = []
for i in range(1, K):
if min(min_ryad[i] - 1, min_ryad[i + 1] - 1) == ans1:
ans2.append(i + 1)

Инициализируем список ans2. Проходим по всем местам от 1 до K-1 и добавляем в ans2 номер места i+1, если максимальный номер ряда перед этими местами равен ans1.
Вывод результата:

Python

print(ans1, max(ans2))

1

print(ans1, max(ans2))

Выводим максимальный номер ряда ans1 и максимальный номер места из списка ans2.

Итог:

Этот код решает задачу нахождения пары соседних кресел в ряду, перед которыми все кресла свободны, а ряд находится как можно дальше от сцены. Используется список min_ryad для хранения минимальных номеров рядов для каждого места, а затем производится поиск максимального номера ряда и соответствующих номеров мест.

Ответ: 9991 5643