Задача D. Трёхцветник ≡

Условие

Куст трёхцветника в начале своего роста выглядит, как три ветки, направленные в разные стороны:

В начале очередного цикла цветения каждая ветка пускает два отростка в разные стороны. При этом, ветка продолжает свой рост. Отростки являются ветками, из которых в начале следующего цикла также начнут появляться новые отростки. Каждая ветка даёт отростки ровно один раз.

После первого и второго циклов цветения трёхцветник примет следующий вид:

Юному садоводу стало интересно узнать количество веток у куста трёхцветника после N циклов цветения.

Требуется написать программу, которая считывает количество циклов цветения, и вычисляет количество веток.

Формат входных данных

Первая строка содержит одно целое число N — количество циклов цветения.

Формат выходных данных

В единственной строке выведите ответ на задачу.

Ограничения

1 ≤ N ≤ 40

Описание системы оценивания

Баллы начисляются пропорционально количеству пройденных тестов.

По запросу сообщается количество набранных баллов.

Примеры тестов

1

9

2

21

Разбор

Решить эту задачу можно несколькими способами.

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

Второй способ: получить ответы для небольших N и попробовать выявить закономерность. Например, первые ответы принимают следующие значения: 9, 21, 45, 93. Можно заметить, что ans_i = 2 ⋅ ans_i − 1 + 3.

Третий способ: также получить ответы для небольших N, но увидеть другую, более сложную, закономерность. Можно заметить, что первый ответ отличается от второго на 21 − 9 = 12, второй от третьего на 45 − 21 = 24, третий от четвёртого на 93 − 45 = 48.

Четвёртый способ: основан на методе динамического программирования. Обозначим за a_i количество веток, которые дадут отростки в i-й цикл цветения, а за b_i — количество веток, которые будут просто расти. Изначально a₁ = 3 и b₁ = 0. После первого цикла цветения a₂ = 6 и b₂ = 3. Получаются следующие формулы для динамики: a_i = 2 ⋅ a_i − 1 и b_i = a_i − 1. Ответом на задачу будет сумма a_N и b_N.

Пятый способ: рассмотрим рост только одной исходной ветки трёхцветника. Можно заметить, что ответы в таком случае будут следующие: 3, 7, 15, 31 и т.д. Эти числа являются степенями двойки минус один. Поэтому можно вывести формулу для быстрого подсчета ответа: ans = (2^N + 1 − 1) ⋅ 3.

Стоит отметить, что при больших N ответ может быть очень большим, поэтому необходимо использовать 64-х битный тип данных. Решения, не учитывавшие данную особенность, могли набрать только 64 балла.