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