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

by

3

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

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


Условие задачи:
http://www.e-olimp.com.ua/problems/3
Прохождение тестов данной программой:
http://www.e-olimp.com.ua/
solutions/1591163

Я разделил задачу на три подэтапа: построение боковой, верхней и задней стен.

Ввод Вывод Комментарий Вердикт
0 0 Проверка на нуль: Пройдено
3 28 Тот же пример что и в условии к задаче: Сходится Проверка пройдена
9 62 1 этап Пройдено
13 83 2 этап Пройдено
19 112 3 этап Пройдено
2Е9 6.00953Е9 Проверка на переполнение максимальным возможным числом: Пройдено

Вначале увидев эту задачу я понял что самое главное в этой задаче это понять какую фигуру лучше строить и как строить. С фигурой все было очевидно: в данном случае самая экономичная фигура это куб, а это значит что нам нужно найти как лучше всего его строить, а если быть более точным как из кубов с величиной стены [latex]I[/latex] построить куб с величиной стены [latex]I+1[/latex]. Я решил что нужно последовательно наращивать стены: вначале боковую, потом верхнюю и напоследок заднюю. Здесь было замечено что количество кубов входящих в нашу фигуру можно найти просто возведя сторону в кубическую степень, с этого и пошли эти строчки:

Вот таким незамысловатым способом мы нашли величину стены у куба если он закончен. Что ж давайте теперь найдем в каком этапе находится строительство куба:

Первый этап(строительство боковой стены):

Второй этап(строительство верхней стены):

Или третий(строительство задней стены):

И мы сразу приступаем к делу: я вывел формулу зависимости количества спичек от фигуры, вот она:
[latex]3xyz+2xy+2xz+2yz+x+y+z[/latex] и из неё я уже вывел эти формулы:
1) Если все стороны равны: [latex]3n(n+1)^2[/latex];

2) Если две стороны равны, а третья на единицу больше: [latex]3n^3 + 9n^2 + 7n + 1[/latex];

3) Если две стороны равны, а третья на единицу меньше: [latex]3n^3 + 3n^2 -n-1[/latex].

Зачем? Первая формула пригодится нам для первого этапа, когда к уже готовому кубу добавляются еще кубы. Вторая: когда после первого этапа одна сторона стала больше чем остальные. И конечно же третья: которая соответственно строится когда две стороны больше третьей.
Теперь нам осталось только достроить недостающие кубы, для этого вначале нужно узнать сколько кубов нужно достроить:
1)Для первого этапа:

2)Для второго:

3)И конечно же для третьего:

Далее нам нужно их построить, здесь все тоже просто они строятся как же как и квадратные числа, всё что нам нужно сделать это найти сколько нужно добавить спичек чтобы достроить еще один куб и когда. Так вот, достройка делается через треугольные числа. Поэтому создается цикл который выдает треугольные числа по порядку и вложенный в него цикл, который проходит все эти треугольные числа:

Зачем нам это нужно? Просто, я заметил что достройка идет по такому принципу(начиная с левого нижнего угла):

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

и в таком порядке:

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

Как вы видите +8 мы видим только на первом кубе, а +5 на первом кубе треугольного и в середине треугольного . Осталось только описать это и мы получаем:

Related Images:

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

  1. Очень хорошо, что удалось решить эту задачу! Молодец!
    — по возможности поправьте орфографию и стилистику
    — ссылку на e-olimp с задачей и пройденными тестами, разместите, пожалуйста в самом начале. И лучше просто две ссылки без пояснений.

  3. — Когда вставляете в текст строки программы отдельно от самой программы, нужно оставлять тот же номер строки. Это позволяет найти место в программе откуда взята строка. Сделать это можно если в разделе «Нумерация» заполнить поле «Начать с».
    Сейчас у всех номер 1. Сбивает.
    — С отступами нужно что-то делать. И в 34-й строке endl должен быть.
    — Для возведения целого числа в квадрат или куб функцию pow() использовать не следует.
    — Для вычисления кубического корня следует использовать функцию pow() а не цикл перебора.

Добавить комментарий