Навигация по странице
Тип 3
К третьему типу отнесём задания, в которых от нас требуется найти места в концертном зале, удовлетворяющие некоторым условиям. Главным условием здесь является отсутствие занятых мест перед выбранными (в последующих рядах).
Сразу перейдём к формулировке задания этого типа:
Задание 2602
«При онлайн-покупке билета на концерт известно, какие места в зале уже заняты. Необходимо купить два билета на такие соседние места в одном ряду, чтобы перед ними все кресла с такими же номерами были свободны, а ряд находился как можно дальше от сцены. Если в этом ряду таких пар мест несколько, найдите пару с наименьшими номерами. В ответе запишите два целых числа: искомый номер ряда и наименьший номер места в найденной паре. Нумерация рядов и мест ведётся с 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 искомую пару найти нельзя»
Самое главное в таких заданиях – понять идею поиска подходящих мест. Начнём с разбора примера к этому заданию. У нас есть некий зал, в котором 7 рядов по 8 мест в каждом.
Отметим красным те места, которые уже заняты.
Итак, по условию нужно найти такую пару соседних мест, перед которыми будут свободны все кресла, при этом ряд находится как можно дальше от сцены. То есть значение ряда должно быть максимально возможным.
В таком подходящем ряду нужно найти наименьшие места, то есть значение места должно быть минимально возможным.
Давайте рассуждать. Логично будет сначала найти первый занятый ряд для каждого места. Для первого места это будет первый ряд, для второго – второй и так далее. Для шестого и седьмого мест таким рядом будет один и тот же – шестой.
Отлично, мы нашли занятые ряды для каждого места. Тогда в какой ряд можно будет сесть с этим же местом? В предыдущий, то есть значение которого на 1 меньше занятого.
Для первого места сесть будет некуда – оно уже занято на самом первом ряду, но вот на втором месте мы можем сесть на первый ряд, на третьем – на третий ряд и так далее. Отметим такие допустимые пары мест жёлтым.
Среди этих мест мы ищем ту пару, которая расположена на максимальном ряду. Здесь таким рядом является пятый (кресла выделены зелёным).
Из этой пары выбираем место с наименьшим значением (левое) – 6. В итоге получаем максимальный ряд 5 и минимальное место 6, что и совпадает с ответом к примеру из условия. Следовательно, наш алгоритм верный, осталось его реализовать в коде.
Начинаем, как и всегда, со считывания данных из файла.
with open('2602.txt') as file:
N, M, K = map(int, file.readline().split())
data = [list(map(int, line.split())) for line in file]
Сразу создадим две переменные, в которые потом поместим значения для ответа.
max_row = 0
min_seat = 0
Теперь нам нужно создать список с первым занятым рядом для каждого места. Но какие значения туда поместить? Поместим туда значения на 1 больше, чем максимальный ряд. И таких значений должно быть на 2 больше, чем количество мест в каждом ряду.
Почему на 2 больше? Потому что дальше мы будем сравнивать пары соседних мест: seat и seat + 1. Чтобы значение seat + 1 для второго места не вышло за границы списка, добавляем лишние 2 элемента. Получаем такое выражение:
min_row = [M + 1] * (K + 2)
Далее нам нужно определить первый занятый ряд для каждого места. В цикле перебираем каждое значение из списка data и проверяем, что значение текущего ряда меньше, чем записанное в списке min_row на позиции текущего места.
for row, seat in data:
if row < min_row[seat]:
min_row[seat] = row
Звучит сложно, но давайте разберём на примере. Первым элементом в списке data будет «50322 175» – номер ряда (row) и номер места (seat).
Значение списка min_row для 175-го места (175-го индекса) будет 99907 – ровно такое же, какое мы и записали при создании этого списка. Число 50322 меньше, чем 99907, значит, перезаписываем в списке min_row значение для 175-го индекса. На текущий момент первым занятым рядом для 175-го места будет 50322-ой ряд.
Теперь, когда мы снова в цикле наткнёмся на строку, в которой фигурирует 175-ое место, например, «7240 175», то значение первого занятого ряда в списке min_row снова обновится и станет равным 7240.
Таким образом, после завершения работы цикла у нас на руках будет список min_row, в котором указан первый занятый ряд для каждого места.
Теперь самое важное и по совместительству самое сложное – нужно пройтись по всем возможным местам и найти максимальный доступный ряд, на который можно купить пару билетов на соседние места.
Цикл будет перебирать целые числа от 1 до K, то есть все места с первого по последнее:
for seat in range(1, K):
Далее в этом цикле мы проверяем допустимый ряд – первый ряд, на который мы можем купить билеты. На изображении выше это как раз ряды с жёлтыми местами.
accept_row = min(min_row[seat], min_row[seat + 1]) - 1
Представим, что seat имеет значение 1. Тогда из списка min_row возвращаются два значения: с индексами 1 и 2. Можем вывести эти значения на экран: для первого места первым занятым рядом будет 75-ый, для второго места – 82660-ый.
Из них определяется минимальное значение первого занятого ряда. В нашем случае – 75. Но это по-прежнему занятый ряд, чтобы получить доступный, надо отнять от него единицу. Тогда, если мы хотим места 1 и 2, то первый допустимый ряд для нас будет 75.
Но мы такие места не хотим – нам нужен максимальный ряд. Значит, пишем такое условие:
if accept_row > max_row or (accept_row == max_row and seat < min_seat):
max_row = accept_row
min_seat = seat
То есть если допустимый ряд больше максимального (который изначально у нас равен 0), то обновляем значение максимального ряда (на допустимый) и места (на значение переменной цикла).
А также если максимальный ряд уже равен допустимому и текущее значение места меньше минимального, то снова обновляем значения максимального ряда и места, точнее, обновится только значение для места.
Такая запись позволяет найти самый дальний возможный ряд и место с наименьшим значением. Вариант с поиском места с наибольшим значением мы рассмотрим в следующей задаче.
На этом решение задачи завершено. Осталось лишь вывести на экран значение наших переменных:
print(f'Наибольший номер ряда: {max_row}')
print(f'Наименьший номер места: {min_seat}')
Полный код будет выглядеть так:
with open('2602.txt') as file:
N, M, K = map(int, file.readline().split())
data = [list(map(int, line.split())) for line in file]
# === Ответы === #
max_row = 0
min_seat = 0
# === === #
# Первый занятый ряд для каждого места
min_row = [M + 1] * (K + 2)
# Определяем первый занятый ряд для каждого места
for row, seat in data:
if row < min_row[seat]:
min_row[seat] = row
# Проходимся по местам и ищем максимальный доступный ряд
for seat in range(1, K):
# Допустимый ряд: на 1 меньше, чем первый занятый
accept_row = min(min_row[seat], min_row[seat + 1]) - 1
if (accept_row > max_row or
(accept_row == max_row and seat < min_seat)):
max_row = accept_row
min_seat = seat
print(f'Наибольший номер ряда: {max_row}')
print(f'Наименьший номер места: {min_seat}')
В ответ записываем два полученных числа: 21028 и 6660.
Пример
Задание 2606
«При онлайн-покупке билета на концерт известно, какие места в зале уже заняты. Необходимо купить два билета на такие соседние места
в одном ряду, чтобы перед ними все кресла с такими же номерами были свободны, а ряд находился как можно дальше от сцены. Если в этом ряду таких пар мест несколько, найдите пару с наибольшими номерами. В ответе запишите два целых числа: искомый номер ряда и наибольший номер места в найденной паре. Нумерация рядов и мест ведётся с 1. Гарантируется, что хотя бы одна такая пара в зале есть.
Входные данные
В первой строке входного файла находятся три числа: N — количество занятых мест в зале (целое положительное число, не превышающее 10000), М — количество рядов (целое положительное число, не превышающее 100 000) и К — количество, мест в каждом ряду (целое положительное число, не превышающее 100 000). В следующих N строках находятся пары натуральных чисел: номер ряда и номер места занятого кресла соответственно (первое число не превышает значения М, а второе — К).
Выходные данные
Два целых положительных числа: наибольший номер ряда и наибольший номер места в найденной паре кресел.
Типовой пример организации данных во входном файле
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 искомую пару найти нельзя»
Обратите внимание, что в этой задаче требуется найти наибольший номер места в найденной паре! В этом и будет единственное отличие в решении этого задания от предыдущего.
В последнем цикле необходимо будет в условии поменять знак у выражения «seat < min_seat» на знак «больше» (название переменной тоже сменим с min_seat на max_seat):
if accept_row > max_row or (accept_row == max_row and seat > max_seat):
А также в конце к переменной max_seat нужно добавить единицу. Ведь в текущем алгоритме мы ищем «левое» место из пары. А для ответа нам нужно именно «правое» место – с наибольшим значением (можно и избежать этого добавления единицы, но тогда придётся менять первую строку последнего цикла и порядок элементов в min_row).
Тогда код для этого задания будет такой:
with open('2606.txt') as file:
N, M, K = map(int, file.readline().split())
data = [list(map(int, line.split())) for line in file]
# === Ответы === #
max_row = 0
max_seat = 0
# === === #
# Первый занятый ряд для каждого места
min_row = [M + 1] * (K + 2)
# Определяем первый занятый ряд для каждого места
for row, seat in data:
if row < min_row[seat]:
min_row[seat] = row
# Проходимся по местам и ищем максимальный доступный ряд
for seat in range(1, K):
# Допустимый ряд: на 1 меньше, чем первый занятый
accept_row = min(min_row[seat], min_row[seat + 1]) - 1
if accept_row > max_row or (accept_row == max_row and seat > max_seat):
max_row = accept_row
max_seat = seat
print(f'Наибольший номер ряда: {max_row}')
print(f'Наибольший номер места: {max_seat + 1}')
В результате получаем два числа: 9991 и 5643, которые и запишем в ответ.