Решение: Поиск пары свободных мест
Организация купила для своих сотрудников все места в нескольких подряд идущих рядах на концертной площадке. Известно, какие места уже распределены между сотрудниками.
Найдите ряд с наибольшим номером, в котором есть два соседних места, такие что слева и справа от них в том же ряду места уже распределены (заняты). Гарантируется, что есть хотя бы один ряд, удовлетворяющий этому условию. В ответе запишите два целых числа: номер ряда и наименьший номер места из найденных в этом ряду подходящих пар свободных мест.
В первой строке входного файла находится число $N$ — количество занятых мест, не превышающее $10\,000$. Каждая из следующих $N$ строк содержит два натуральных числа, не превышающих $100\,000$: номер ряда и номер занятого места.
Выведите два целых неотрицательных числа: номер ряда и наименьший номер места в выбранной паре.
Решение по шагам
4 шагаСгруппируем занятые места по номерам рядов и отсортируем номера мест внутри каждого ряда.
Рассмотрим две соседние в отсортированном списке занятые места $x$ и $y$. Между ними могут находиться две соседние свободные позиции, ограниченные занятыми местами слева и справа, если $y-x\geq 3$.
$$y-x\geq 3$$Наименьшая подходящая пара между такими занятыми местами начинается с места $x+1$, а заканчивается местом $x+2$.
$$(x+1,\ x+2)$$Для каждого ряда запоминаем минимальное найденное начало пары. Затем выбираем ряд с максимальным номером; если в нём несколько пар, оставляем минимальный номер места.
Номер ряда с максимальным номером и минимальное начало подходящей пары свободных мест, вычисленные по входному файлу.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Проверяют только наличие двух свободных мест, но не проверяют занятость мест слева и справа.
Выбирают ряд с минимальным, а не с максимальным номером.
Выводят второе свободное место вместо наименьшего номера места в паре.
Не сортируют номера мест внутри каждого ряда перед проверкой промежутков.