Решение: Коробки-матрёшки
В магазине есть $N$ кубических коробок. Одну коробку можно поместить в другую, если длина её стороны хотя бы на 3 единицы меньше длины стороны другой коробки. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки в таком наборе. Размер подарка позволяет поместить его в самую маленькую коробку.
Во входном файле в первой строке указано число $N$, затем в $N$ строках — длины сторон коробок. Запишите сначала наибольшее количество коробок, затем максимально возможную длину стороны самой маленькой коробки.
Решение по шагам
4 шагаСчитаем все длины сторон коробок и сортируем их по возрастанию.
$$a_1 \leq a_2 \leq \dots \leq a_N$$Последовательно строим цепочку. Очередную коробку можно добавить, если её сторона отличается от стороны последней выбранной коробки не менее чем на 3.
$$a_i-a_{last}\geq 3$$Для каждой максимальной по длине цепочки запоминаем длину её первой коробки. Если длина цепочки увеличилась, заменяем ответ; если длина такая же, выбираем большую первую сторону.
Конкретные два числа определяются значениями из прилагаемого входного файла, содержимое которого в условии не приведено.
Определяется по данным прилагаемого файла
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Используют разность менее 3 между соседними коробками.
Не сортируют длины сторон перед построением цепочки.
При одинаковом максимальном количестве коробок выбирают не максимальную, а минимальную сторону самой маленькой коробки.