Решение: Упаковка коробок матрёшкой
В магазине для упаковки подарков есть $N$ кубических коробок. Подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и так далее. Одну коробку можно поместить в другую, если длина её стороны хотя бы на 13 единиц меньше длины стороны другой коробки. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки в таком наборе. Размер подарка позволяет поместить его в самую маленькую коробку.
Входной файл содержит в первой строке число $N$, а в следующих $N$ строках — длины сторон коробок. Все значения — натуральные числа, не превышающие 10 000. Для выполнения задания используйте данные из прилагаемого файла.
Решение по шагам
4 шагаСчитайте из файла все длины сторон коробок и отсортируйте их по возрастанию. Одинаковые коробки можно учитывать отдельно, но использовать две коробки одинакового размера одна внутри другой нельзя.
Для каждой коробки определите максимальную длину цепочки, заканчивающейся этой коробкой. Предыдущая коробка должна иметь длину стороны не более $a_i - 13$.
Если максимальная длина цепочки равна $L$, то среди всех цепочек длины $L$ выберите ту, у которой размер самой маленькой коробки максимален.
В ответ выведите найденное максимальное количество коробок и соответствующую максимальную длину стороны самой маленькой коробки.
Определяется по данным прилагаемого входного файла.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Проверяют разницу между соседними коробками меньше 13 вместо условия не менее 13.
Используют коробки одинакового размера в одной цепочке.
При равном количестве коробок не выбирают цепочку с максимально возможной самой маленькой коробкой.
Считают пример из условия исходными данными задания.