4368. Треугольная паутина

Перед вами бесконечная треугольная решётка. Она устроена так, что если поджечь некоторую вершину, то в момент времени 0 загорится эта вершина, через одну секунду загорятся все вершины, непосредственно соседние с ней, затем – все вершины, соседние с уже горящими, и так далее. Считайте, что огонь никогда не гаснет.

Изначально подожжена одна вершина. Определите количество горящих вершин через n секунд.

Вход. Одно целое  число n (0 ≤ n ≤ 10⁹).

Выход. Выведите количество горящих вершин через n секунд.

Пример входа 1	Пример выхода 1
1	7
Пример входа 2	Пример выхода 2
1500	6754501

РЕШЕНИЕ

комбинаторика

Анализ алгоритма

Рассмотрим, как распространяется огонь на бесконечной треугольной решётке:

1. Начальная вершина. В момент времени 0 горит только начальная вершина. Это даёт первую единицу в общем числе горящих вершин.

2. Первый уровень (через 1 секунду). Вершины, которые непосредственно соседствуют с начальной, загорятся через 1 секунду. В треугольной решётке каждая вершина имеет 6 соседей. Следовательно, первый уровень содержит 6 вершин.

3. Второй уровень (через 2 секунды). На следующей секунде загорятся вершины, которые соседствуют с уже горящими вершинами первого уровня, но ещё не горят. Второй уровень содержит 12 вершин.

Можно заметить закономерность: каждый новый уровень добавляет на 6 вершин больше, чем предыдущий.

· Первый уровень: 6 вершин

· Второй уровень: 12 вершин

· Третий уровень: 18 вершин

· … и так далее.

Получаем арифметическую прогрессию с первым членом a₁ = 6 и разностью d = 6.

Через n секунд количество горящих вершин будет равно

res = 1 + (6 + 12 + 18 + … + (6 + 6(n – 1)))

Используя формулу суммы арифметической прогрессии , получим что

res = 1 + = 1 + (6 + 3(n – 1))n = 1 + 3n(n + 1)

Реализация алгоритма

Читаем входное значение n.

scanf("%lld",&n);

Вычисляем и выводим ответ.

res = 1 + 3 * n * (n + 1);

printf("%lld\n",res);