Поиск соседних свободных мест
При онлайн-покупке билета на концерт известно, какие места в зале уже заняты. Необходимо купить два билета на такие соседние места в одном ряду, чтобы перед ними все кресла с такими же номерами были свободны, а ряд находился как можно дальше от сцены. Если в этом ряду таких пар мест несколько, найдите пару с наименьшими номерами. Нумерация рядов и мест ведётся с 1. Гарантируется, что хотя бы одна такая пара в зале есть.
Задание выполняется с использованием прилагаемого файла. В первой строке входного файла находятся три числа: $N$ — количество занятых мест в зале, $M$ — количество рядов, $K$ — количество мест в каждом ряду. В следующих $N$ строках находятся пары натуральных чисел: номер ряда и номер места занятого кресла соответственно. Требуется определить наиболее удалённый от сцены ряд, в котором есть пара соседних свободных мест, перед которой все места с такими же номерами во всех предыдущих рядах свободны. В найденном ряду нужно выбрать пару с наименьшими номерами.
Условие как в банке ФИПИ — открыть и сверить
| ||||||
| | ||||||
Формат: число или слово без единиц измерения; дробную часть отделяйте запятой.
1Мягкая — с чего смотретьуровень 1 из 3
Для каждой пары соседних мест проверьте, свободны ли места с теми же номерами во всех рядах, расположенных ближе к сцене.
2Наводящая — какие числа считатьуровень 2 из 3
Удобно хранить занятые места по рядам и рассматривать ряды в порядке возрастания номеров. Подходящая пара в ряду начинается с места $j$, если места $j$ и $j+1$ свободны в этом ряду, а в каждом предыдущем ряду хотя бы одно из этих мест не занято.
3Прямая — фактически решениеуровень 3 из 3
Просмотрите все ряды и сохраните последний ряд, в котором найдена подходящая пара. В этом ряду запишите минимальное значение $j$.