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