Решение: Поиск пары свободных мест
Организация купила для своих сотрудников все места в нескольких подряд идущих рядах на концертной площадке. Известно, какие места уже распределены между сотрудниками. Найдите ряд с наибольшим номером, в котором есть два соседних места, таких что слева и справа от них в том же ряду места уже распределены (заняты). Гарантируется, что есть хотя бы один ряд, удовлетворяющий этому условию. В ответе запишите два целых числа: номер ряда и наименьший номер места из найденных в этом ряду подходящих пар.
Входные данные
В первой строке входного файла находится число $N$ — количество занятых мест (натуральное число, не превышающее 10\,000). Каждая из следующих $N$ строк содержит два натуральных числа, не превышающих 100\,000: номер ряда и номер занятого места.
Выходные данные
Два целых неотрицательных числа: номер ряда и наименьший номер места в выбранной паре.
Пример входного файла: 7; далее пары: (40, 3), (40, 6), (60, 33), (50, 125), (50, 128), (50, 64), (50, 67). Для приведённого примера подходящие пары имеют вид (40, 4), (50, 126), (50, 65), поэтому ответ: 50 65.
Решение по шагам
4 шагаУдобно хранить для каждого ряда множество занятых мест, чтобы проверять принадлежность за постоянное время.
$$occupied[row] = \{\text{занятые места в ряду}\}$$Две соседние свободные места с занятыми местами слева и справа имеют вид $x+1$ и $x+2$, при этом места $x$ и $x+3$ заняты, а $x+1$ и $x+2$ не заняты.
$$x \in occupied,\quad x+1 \notin occupied,\quad x+2 \notin occupied,\quad x+3 \in occupied$$Для каждого ряда перебираем занятые места как возможное левое ограничение, находим минимальный номер подходящей пары и сравниваем ряд с текущим лучшим рядом.
Если номер ряда больше текущего максимального, заменяем ответ. Если ряд тот же, сохраняем меньший номер места.
Вывести максимальный номер подходящего ряда и минимальный номер места в паре свободных мест этого ряда.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Выбирать ряд с наименьшим, а не с наибольшим номером.
Проверять только расстояние между занятыми местами и не убеждаться, что оба внутренних места свободны.
Выбирать произвольную пару в найденном ряду вместо пары с наименьшим номером места.
Считать подходящей пару из одного свободного места или пару, для которой занято только одно внешнее место.