e-olymp 3. Спичечная модель

Спичечная модель

Спичечная модель с http://www.e-olimp.com.ua/problems/3

Задача.

Профессор Самоделкин решил изготовить объемную модель кубиков из спичек, используя спички для рёбер кубиков. Длина ребра каждого кубика равна одной спичке.

Для построения модели трех кубиков он использовал [latex]28[/latex] спичек.

Какое наименьшее количество спичек нужно Самоделкину для построения модели из N кубиков?

Все числа в задаче не превышают [latex]2*10^9[/latex].

Технические условия

Входные данные

Одно число [latex] N [/latex] – количество кубиков.

Выходные данные

Одно число – количество спичек.

 

Ссылка на саму задачу.

Пройденные тесты программы.

Input Output Comments
0 0 Смотрим,что выдает при  0 кубов
3 28 Проверяем пример данный в задаче
[latex]2*10^9[/latex] 6.00953Е9 Не вылезает ли за рамки переменных

Для решения задачи желательно придумать, как мы будем строить спичечную модель. Самый оптимальный и правильный вариант — это строить в форме куба. (если не верите, поэкспериментируйте с другими формами построения)

Для лучшего понимания сколько нам понадобится спичек, рекомендую представить на бумаге как будут выглядеть «этажи» нашего куба.

Первый этаж будет выглядеть так. (Для примера берем куб [latex]444[/latex], т.к. он самый наглядный и не громоздкий)

8 5 5 5
8 5 5 5
8 5 5 5
12 8 8 8

Для построения самого первого куба нам понадобится 12 спичек, для достройки к нему второго и третьего понадобится по 8, для достройки четвертого куба уже понадобится 5 и так далее.

Второй этаж будет выглядеть так. (аналогично для последующих)

5 3 3 3
5 3 3 3
5 3 3 3
8 5 5 5

Поскольку у нас уже есть основание, то последующие этажи требуют меньшего количества спичек. Зная это, выведем формулу, по которой можно вычеслить необходимое количество спичек для построения куба [latex]n[/latex]-ой размерности.

Получаем [latex]8i+4+5i(i-1)2+3(i-1)2+3i(i-1)^2+2(i-1)^2[/latex] (Где i — это «размерность» куба. К примеру: подставив i=4, мы найдем необходимое количество спичек для построение куба [latex]44*4[/latex]).

Теперь возник вопрос, как в задаче определить размерность куба? Очень просто. Максимальное количество возможных кубов равно [latex]i^3[/latex], следовательно зная количество кубов (Дано в начале задачи) можно определить [latex]i[/latex]. Описываем цикл, увеличивающий [latex]i[/latex] пока [latex]i^3<n[/latex].

Задаем функцию с тремя параметрами. ([latex]u[/latex] — определяет, в какую степень возводить)

Имея размерность, можно узнать, сколько нам надо спичек для построения куба прошлой размерности по формуле. Следовательно мы знаем, сколько кубов принадлежит размерности [latex]i[/latex] ([latex]p=n-i^3[/latex]). Разобьем на этапы построение куба размерности [latex]i[/latex] из куба размерности [latex]i-1[/latex]. Пример:

Имея куб [latex]333[/latex] мы начнем достраивать к нему боковую стенку, потом заднюю, и в самом конце так называемую «крышу».

При построении боковой стены мы получаем куб равный [latex] 433[/latex](увеличилась его длинна).

Вид сверху:

[ ] [ ] [ ] [ ]
[ ] [ ] [ ] [ ]
[ ] [ ] [ ] [ ]

При построении задней стены он расшириться в ширине [latex]443[/latex].

[ ] [ ] [ ] [ ]
[ ] [ ] [ ] [ ]
[ ] [ ] [ ] [ ]
[ ] [ ] [ ] [ ]

На третьем этапе увеличиться высота куба. Следовательно куб будет иметь такую форму [latex]444[/latex].

Определяем  этап. Если мы находимся на третьем этапе, то разность между количеством кубов([latex]n[/latex]) и количеством кубов нашей размерности без крыши([latex]i^2(i-1)[/latex] должно быть больше нуля — [latex]n-i^2(i-1)>0[/latex]. Если больше нуля, то переходим к третьем этапу, иначе смотрим, не на первом ли мы этапе случайно? Для этого количество кубов([latex]n[/latex]) должно быть меньше или равно количеству кубов на первом этапе нашей размерности([latex]i(i-1)(i-1)[/latex]) — [latex]i(i-1)(i-1)>=n[/latex]. Если это выполняется, то переходим к первому этапу, иначе ко второму этапу.

Этап определён. Осталось придумать самый экономный способом построения оставшихся кубов. (В этом и заключается подвох задачи) Самый экономный способ, это если мы будем строить боковую стенку (заднюю или «крышу») в такой последовательности:

16 15 14 13
9 8 7 12
4 3 6 11
1 2 5 10

В количестве затраченных спичек выглядит вот так:

3 3 3 5
3 3 5 3
3 5 3 3
8 5 5 5

По диагонали и по основанию мы тратим по 5 спичек, остальные кубы требуют  по 3 (для построения первого куба необходимо 8 спичек). Можно заметить, что номера кубов, для построения которых надо 5 спичек, имеют зависимость, которую можно использовать. По размерности боковой плоскости можно определить количество спичек необходимых для построения плоскости прошлой размерности по формуле [latex]8+(g-2)25+3((g-1)(g-1)-1-(g-2)2)[/latex]. Формула при размерности 1 выдаст неправильный ответ, по этому ставим условие, если [latex]g=1[/latex], то результат увеличиваем на 8, иначе на всю эту формулу. После этого у нас осталость некое количество кубов. Запускаем цикл от номера последнего элемента нашей прошлой разрмерности latex(g-1)+i<=p[/latex].

Разобравшись во всех нюансах задачи, приступаем к напсианию кода.

Ссылка на программу

Related Images: