Спичечная модель | C++ для приматов

Спичечная модель с 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] — определяет, в какую степень возводить)

int bit(int i,int n,int u)
{
    do
    {
        i=i+1;
    }while(pow(i,u)<n);
    return i;
}

int bit(int i,int n,int u)

{

i=i+1;

}while(pow(i,u)<n);

return i;

}

Имея размерность, можно узнать, сколько нам надо спичек для построения куба прошлой размерности по формуле. Следовательно мы знаем, сколько кубов принадлежит размерности [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].

for (long int i = 1;(g-1)*(g-1)+i <= p;i++)
{
    if ((i == 1 || i == g) && g != 1)
    {
        result+=5;
    }
    else if (g != 1)
    {
        result+=3;
    }
}

for (long int i = 1;(g-1)*(g-1)+i <= p;i++)

{

if ((i == 1 || i == g) && g != 1)

{

result+=5;

}

else if (g != 1)

{

result+=3;

}

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

#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;

int bit(int i,int n,int u)
{
    do
    {
        i=i+1;
    }while(pow(i,u)<n);
    return i;
}


int main() {
double n,result,p;//переменные для результата и количество кубиков,на всякий случай большой размерности
long long int i=0,g=0;//объявляем переенные для разрядностей
cin>>n;
i=bit(i,n,3);//находим разрядность куба
if ((i*i*(i-1))>=n)//проверка третьего этапа
    {
        if (((i-1)*(i-1)*i)>=n)//проверка первого этапа и если правда,то решение первого этапа
        {
            double o=i-1;
            result=8*o+4+5*o*(o-1)*2+3*(o-1)*2+3*o*(o-1)*(o-1)+2*(o-1)*(o-1);//результату присваем прошылй куб
            p=n-o*o*o;//количество оставшихся кубов
            g=bit(g,p,2);//разрядность плоскости
            if (g==1)//проверка разрядности на 1
                result+=8;//увеличение результата на 8 при разрядности 1
            else
                result+=8+(g-2)*2*5+3*((g-1)*(g-1)-1-(g-2)*2);//увеличение результата по формуле
            for (long int i = 1;(g-1)*(g-1)+i <= p;i++)
            {
                if ((i == 1 || i == g) && g != 1)
                {
                    result+=5;
                }
                else if (g != 1)
                {
                    result+=3;
                }
            }
             
        }
        else//решение второго этапа
        {
            double o=i-1;
            result=8*o+4+5*o*(o-1)*2+3*(o-1)*2+3*o*(o-1)*(o-1)+2*(o-1)*(o-1)+o*o*3+5+2*2*(o-1);//результат по формуле+ещё достроеная на первом этапе стенка
            p=n-o*o*(o+1);
            g=bit(g,p,2);
            if (g==1)
                result+=8;
            else
                result+=8+(g-2)*2*5+3*((g-1)*(g-1)-1-(g-2)*2);
            for (long int i=1;((g-1)*(g-1)+i)<=p;i++)
            {
                if ((i == 1 || i == g) && g != 1)
                {
                    result+=5;
                }
                else if (g!=1)
                {
                    result+=3;
                }
            }
        }
    }
    else//решение третьего этапа
    {
        double o=i;
        result=8*(o-1)+4+5*(o-1)*(o-1)*2+3*(o-1)*2+3*(o-1)*(o-1)*(o-1)+2*(o-1)*(o-1);//результат по формуле разрядности,только на высоту раную i-1
        p=n-(o-1)*o*o;
            g=bit(g,p,2);
        if (g==1)
            result+=8;
        else
            result+=8+(g-2)*2*5+3*((g-1)*(g-1)-1-(g-2)*2);
        for (long int i=1;((g-1)*(g-1)+i)<=p;i++)
        {
            if ((i == 1 || i == g) && g != 1)
            {
                result+=5;
            }
                else if (g!=1)
            {
                result+=3;
            }
        }
    }
 cout <<result<< endl;
    return 0;
}