Решение: Коржи для многоярусного торта
В кондитерской есть $N$ круглых форм для коржей. Специализация кондитерской — многоярусные торты, в которых диаметр каждого верхнего коржа меньше диаметра предыдущего. Один корж можно поместить на другой, если его диаметр хотя бы на 4 единицы меньше диаметра другого коржа. Определите наибольшее количество коржей, которое можно использовать для создания многоярусного торта, и максимально возможный диаметр самого маленького коржа.
В первой строке входного файла находится число $N$ — количество форм для коржей в кондитерской. В следующих $N$ строках находятся значения диаметров форм для коржей, каждое — в отдельной строке. Диаметр формы равен диаметру коржа, который выпекается в этой форме.
Запишите два целых числа: сначала наибольшее количество коржей, которое можно использовать для создания одного многоярусного торта, затем максимально возможный диаметр самого маленького коржа в таком торте.
Для выполнения задания используйте данные из прилагаемого входного файла.
Решение по шагам
3 шагаСортируем все диаметры по убыванию. Для каждого выбранного коржа следующий можно взять только тогда, когда разность диаметров соседних выбранных коржей не меньше 4.
$$d_i - d_{i+1} \geq 4$$Одним проходом по отсортированному массиву строим максимально длинную последовательность: берём очередной диаметр, если он удовлетворяет условию относительно последнего выбранного.
Число выбранных коржей является первым числом ответа. Последний выбранный диаметр — максимально возможный диаметр самого маленького коржа среди цепочек максимальной длины.
Точный ответ определяется содержимым прилагаемого входного файла, которое не представлено в условии.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Используют разность меньше 4 вместо условия не менее 4.
Сортируют диаметры по возрастанию и неправильно интерпретируют порядок ярусов.
Максимизируют диаметр самого маленького коржа, не обеспечив максимальное количество коржей.
Учитывают только различные диаметры и теряют доступные формы одинакового диаметра.