Задачу можно решать последовательными улучшениями.
\(O(n^3)\) — 20 баллов
Переберем все тройки натуральных чисел \(a,b,c\le n\). Рассмотрим прямоугольный параллелепипед со сторонами \((a,b,c)\). Площадь поверхности этого параллелепипеда есть \(2ab+2ac+2bc=S\). Среди всех таких, что \(S\le n\), найдём тот, объём которого максимален.
\(O(n^2)\) — 30 баллов
Зафиксируем две стороны \(a\) и \(b\). Зададимся вопросом, какой может быть третья сторона. Из неравенства \(2ab+2ac+2bc\le n\) получаем, что \(c\le\frac{n-2ab}{2a+2b}\). Таким образом, достаточно рассмотреть только \(c=\left\lfloor\frac{n-2ab}{2a+2b}\right\rfloor\). Перебирая все пары \(a,b\le n\), получаем решение за \(O(n^2)\).
\(O(n\log n)\) — 60 баллов
Для того, чтобы ещё сильнее ускорить решение, заметим, что имеет смысл перебирать только такие стороны \(a\) и \(b\), что \(ab\le n\). Количество таких пар есть \(\)\sum^n_{a=1}\frac na=n\sum^n_{a=1}\frac1a=O(n\log n).\(\) Аналогичная идея применяется при оценке времени работы алгоритма Эратосфена.
\(O(n)\) — 70 баллов
Описанное выше рассуждение можно ещё улучшить. Предположим, что \(a\le b\le c\) — стороны параллелепипеда. Тогда \(a,b\le\sqrt{n/2}\). Действительно, если предположить обратное, то \(b,c>\sqrt{n/2}\Rightarrow2bc>n\). Исходя из этого наблюдения, достаточно перебрать \(O(n)\) пар значений \((a,b)\).
\(O(\sqrt n)\) — 100 баллов
Основная идея решения заключается в исследовании границ, в которых лежит оптимальный ответ. Кратко опишем ключевые моменты:
Если стороны параллелепипеда можно было бы делать вещественными, то оптимальный ответ достигался бы при \(a=b=c=\sqrt{n/6}\).
Положим \(a=\left\lfloor\sqrt{n/6}\right\rfloor\).
Будем последовательно уменьшать \(a\), пока оптимальный ответ при фиксированном \(a\) и вещественных \(b\) и \(c\) не станет хуже лучшего из найденных.
Убедимся, что даже для \(n\) порядка \(10^{13}\) потребуется перебрать не очень много значений \(a\). Это легко можно сделать, проведя численный эксперимент.
Аналитические же выкладки довольно громоздки и показывают, что достаточно перебрать порядка \(\sqrt[4]n\) значений \(a\).
При фиксированном значении \(a\) оптимальный ответ достигается при \(b=c=\sqrt{a^2+n}-a\).
Положим \(b=\left\lfloor\sqrt{a^2+n}-a\right\rfloor\).
Будем последовательно уменьшать \(b\), пока оптимальный ответ при фиксированных \(a\), \(b\) и вещественном \(c\) не станет хуже лучшего из найденных.
Снова убедимся, что требуется перебрать небольшое количество различных значений \(b\) (порядка \(\sqrt[4]n\)).
Суммарное время работы программы есть \(O(\sqrt n)\).
Существует также альтернативный подход к получению верного решения. Тем или иным способом догадавшись, что ответ надо искать вблизи \(\sqrt{n/6}\), можно перебрать значения, отстоящие от этого значения не более чем на \(\Delta\). Из предыдущего решения следовало, что \(\Delta\) следует задавать порядка \(\sqrt[4]n\). Такое решение также имеет асимптотику \(O(n^{1/2})\).
Начинающий программист Поликарп очень любит дарить подарки, особенно в коробках. Он давно заметил, что если коробка красиво оформлена, то радость от подарка возрастает многократно. Любой обёрточной бумаге он предпочитает клетчатую. В самом деле, после распаковки подарка на ней можно играть в крестики-нолики, морской бой, точки, а также решать задачи и писать программы.
Поликарп очень аккуратен. Он упаковывает подарок в коробку, имеющую форму прямоугольного параллелепипеда, и оклеивает всю её поверхность клетчатой бумагой. При этом каждая грань коробки представляет собой прямоугольник, состоящий из целых клеток. На рисунке изображён пример такой упаковки подарка.
В настоящий момент Поликарп собирается поздравить свою подругу, недавно вернувшуюся с очередной олимпиады. Он хочет подарить ей подарок в большой и красивой коробке.
У Поликарпа в наличии есть лист клетчатой бумаги, состоящий из \(n\) клеток. Каким будет максимальный объём коробки, которую можно оклеить с использованием этого листа бумаги описанным выше способом? Поликарп может разрезать лист клетчатой бумаги по границам клеток произвольным образом и оклеивать коробку получившимися фигурами, поэтому форма листа не важна, а имеет значение только количество клеток на нём. Поликарп может использовать для оклеивания коробки не все клетки.
Напишите программу, которая по заданному количеству клеток \(n\) находит размеры коробки максимального возможного объема.
Выходные данные
Выведите в первую строку выходного файла максимальный объём коробки, которую может подарить Поликарп. Объём следует выводить в «кубических клетках», то есть единицей измерения является куб со стороной, равной длине стороны клетки.
Во вторую строку выведите ширину, длину и высоту искомой коробки. Единица измерения — размер клетки. Числа разделяйте пробелами. Если решений несколько, то выведите любое из них.
Система оценивания
Решения, корректно работающие при \(n\le5\,000\), будут оцениваться из 30 баллов, а решения, корректно работающие при \(n\le10^8\), будут оцениваться из 70 баллов.