Центр "Стратегия" Базовый курс С

Задача №2529. Подарок

Задачу можно решать последовательными улучшениями.

\(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})\).

Сдать: для сдачи задач необходимо войти в систему