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