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