Задание 26 ЕГЭ по информатике · AD6F70

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

1. Считайте из файла количество занятых мест и занесите пары «ряд — место» в структуру данных, позволяющую быстро проверять занятость кресла.

2. Для каждого ряда и каждого начала пары j от 1 до K−1 проверьте, свободны ли места j и j+1 в текущем ряду.

3. Для найденной пары проверьте все предыдущие ряды: места j и j+1 с такими же номерами должны быть свободны в каждом из них.

4. Среди подходящих пар выберите максимальный номер ряда, а в этом ряду — минимальный номер первого места пары.