Решение: Поиск пары свободных мест
Организация купила для своих сотрудников все места в нескольких подряд идущих рядах на концертной площадке. Известно, какие места уже распределены между сотрудниками. Найдите ряд с наибольшим номером, в котором есть два соседних места, таких что слева и справа от них в том же ряду места уже распределены (заняты). Гарантируется, что есть хотя бы один ряд, удовлетворяющий этому условию. В ответе запишите два целых числа: номер ряда и наименьший номер места из найденных в этом ряду подходящих пар.
В первой строке входного файла находится число 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.
Напишите программу, которая обрабатывает данные из входного файла и выводит номер выбранного ряда и наименьший номер места в подходящей паре.
Решение по шагам
4 шагаСгруппируем занятые места по номерам рядов и отсортируем номера мест внутри каждого ряда.
$$r \to [m_1, m_2, \ldots, m_k]$$Два соседних свободных места, ограниченные занятыми местами слева и справа, находятся между двумя занятыми местами, номера которых отличаются на 3.
$$m_{i+1}-m_i=3 \Rightarrow (m_i+1,\ m_i+2)$$Для каждой найденной пары запоминаем номер ряда и первое свободное место. Затем выбираем максимальный номер ряда, а при необходимости — минимальный номер места.
$$\max r,\quad \min(m_i+1)$$Для примера в ряду 40 подходит пара мест 4 и 5, а в ряду 50 — пары 65 и 66, 126 и 127. Поэтому выбирается ряд 50 и место 65.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Проверяют разность 2 вместо разности 3 между номерами занятых мест.
Выбирают ряд с наименьшим, а не с наибольшим номером.
Не сортируют номера мест внутри ряда перед поиском пары.
Выводят второе место пары вместо наименьшего.