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