Решение: Выбор места в зале
При онлайн-покупке билета на концерт известны номера занятых мест в зале. Необходимо выбрать свободное место так, чтобы перед ним было как можно больше подряд идущих свободных кресел с тем же номером места. Если подходящие места есть в нескольких рядах, выберите ряд, расположенный ближе к сцене. Данные для решения находятся в прилагаемом файле.
В первой строке файла указаны $N$, $M$ и $K$: количество занятых мест, количество рядов и количество мест в каждом ряду. В следующих $N$ строках записаны пары: номер ряда и номер занятого места. Выведите номер выбранного ряда и количество свободных кресел перед выбранным местом.
Решение по шагам
4 шагаСгруппировать занятые места по номерам рядов.
Для каждого ряда упорядочить номера занятых мест по возрастанию.
Проверить свободные кресла перед первым занятым местом, между соседними занятыми местами и перед концом ряда. Для соседних занятых мест с номерами $a$ и $b$ длина промежутка равна $b-a-1$.
Выбрать максимальный найденный промежуток. Если одинаковый максимум встречается в нескольких рядах, выбрать ряд с меньшим номером.
Числовой ответ зависит от данных прилагаемого файла.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Не учитывать свободные места перед первым занятым креслом.
Считать занятое кресло частью свободного промежутка.
При равенстве длины промежутков выбирать не ближайший к сцене ряд.
Путать номер ряда с количеством свободных кресел.