Решение: Поиск пары соседних мест
При онлайн-покупке билета на концерт известно, какие места в зале уже заняты. Необходимо купить два билета на такие соседние места в одном ряду, чтобы перед ними все кресла с такими же номерами были свободны, а ряд находился как можно дальше от сцены. Если в этом ряду таких пар мест несколько, найдите пару с наибольшими номерами. Нумерация рядов и мест ведётся с 1. Гарантируется, что хотя бы одна такая пара в зале есть.
Задание выполняется с использованием прилагаемого файла. Во входном файле в первой строке заданы $N$, $M$ и $K$: количество занятых мест, количество рядов и количество мест в каждом ряду. В следующих $N$ строках указаны номер ряда и номер занятого места. Определите наибольший номер ряда и наибольший номер места в найденной паре кресел.
Решение по шагам
4 шагаСгруппируем занятые места по номерам рядов и для каждого ряда определим максимальный номер занятого места.
В ряду с максимальным занятым номером $q$ подходящая пара может начинаться только после этого места. Поэтому проверяем места $q+1$ и $q+2$: если они существуют, то пара $q+1$, $q+2$ свободна, а перед ними нет занятых мест.
Для каждого ряда, в котором существует такая пара, сохраняем номер ряда и наибольший номер места. Выбираем запись с максимальным номером ряда; при необходимости в этом ряду выбираем пару с наибольшими номерами.
Конкретные два числа считываются из прилагаемого входного файла.
Определяется по данным прилагаемого файла.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Выбирать ряд с наибольшим номером без проверки существования подходящей пары.
Проверять только соседство мест и не учитывать условие о свободных креслах перед ними.
Записывать первое место пары вместо наибольшего номера места.