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

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

Спичечная модель с 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]4*4*4[/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]8*i+4+5*i*(i-1)*2+3*(i-1)*2+3*i*(i-1)^2+2*(i-1)^2[/latex] (Где i — это «размерность» куба. К примеру: подставив i=4, мы найдем необходимое количество спичек для построение куба [latex]4*4*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]3*3*3[/latex] мы начнем достраивать к нему боковую стенку, потом заднюю, и в самом конце так называемую «крышу».

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

Вид сверху:

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

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

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

На третьем этапе увеличиться высота куба. Следовательно куб будет иметь такую форму [latex]4*4*4[/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)*2*5+3*((g-1)*(g-1)-1-(g-2)*2)[/latex]. Формула при размерности 1 выдаст неправильный ответ, по этому ставим условие, если [latex]g=1[/latex], то результат увеличиваем на 8, иначе на всю эту формулу. После этого у нас осталость некое количество кубов. Запускаем цикл от номера последнего элемента нашей прошлой разрмерности [latex](g-1)*(g-1)+i<=p[/latex].

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

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

2 thoughts on “Спичечная модель

  1. Хорошая работа. Только вычитайте её, пожалуйста (исправьте опечатки и ошибки). Если можно, обойдёмся без фамильярностей в обращении. Сконцентрируйтесь на сути. Это ведь учебная работа, а не пост на молодёжном форуме.
    Нужно хоть раз внимательно прочитать свою работу. Вам самому захочется поработать над стилем и терминологией. Например, разрядность числа в математике — количество числовых разрядов, необходимых для записи этого числа в той или иной системе счисления. Вы это имели в виду?

  2. Сразу хочу сказать, что Вы молодец, что справились в самом начале обучения с такой сложной задачей. Но замечаний по решению и оформлению довольно много.

    По решению. То, что на сайте решение принято это очень хорошо, но программа нуждается в существенном рефакторинге.
    — Меня смущает использование чисел с плавающей точкой для подсчетов количества спичек. Оно ведь подразумевается целым? Например для последнего теста ответ должен быть 6009528744, а не то округленное значение, которое Вы выдаете за правильный ответ.
    — Вам в нескольких местах нужно вычислить квадратный корень, а в одном — кубический. Вы для этого пишите свою функцию bit в которой используется цикл с вызовом функции pow(), которая и сама умеет вычислять корень. Это точно нужно убрать.
    — Три случая, которые Вы рассматриваете имеют очень много общего. Нужно хорошенько все продумать и в несколько раз уменьшить объем кода.
    — Слова размерность и разрядность в комментариях употребляются не к месту.

    По оформлению.
    Позволил себе немного отредактировать текст:
    — Исправил орфографические ошибки (они в редакторе подчеркнуты красным).
    — Удалил пустые строки.
    — Убрал слово «Самый» из «Самый оптимальный» как бессмысленное (прилагательное оптимальный соответствует «минимальный» или «максимальный» и не имеет степеней).
    — Убрал слово «оптимальный» из «Самый оптимальный» поскольку такие заявления принято доказывать или хотя бы обосновывать.
    — Добавил пробелы после знаков препинания.
    — Заменил неудачные выражения типа «вылезает» на что-то более нейтральное.
    — Дойдя до выражения «размерность куба» понял , что слишком вмешиваюсь в Вашу работу и отменил исправления….

    Анатолий!
    Размерность куба — 3 (три). Если Вам нужны другие размерности, то это гиперкуб. Но, скорее всего, Вы просто путает размерность и размер.
    В комментариях к программе встречается «разрядность плоскости». Гугл утверждает, что Вы единственный человек в мире употребивший такое словосочетание. Или подробно опишите, какой смысл Вы в него вкладываете, или (лучше!) замените на какой-то общеупотребительный термин.