Question

Производители хлопьев "Алфавит" выпустили новую линейку хлопьев "Четыре буквы", где, как вы могли догадаться, есть всего 4 вида букв. Ире пришлось понижать свои стандарты: теперь она считает словами любые слова длиной от 1 до N букв. Сколько слов она сможет составить на этот раз? python

Answer 1

Алгоритм: на каждой позиции может быть одна из четырёх букв. Значит, если слово состоит из k букв, то количество слов ровно 4^k, Значит, всего слов 4 + 4² + 4³ + ... + 4ⁿ. Можно реализовать цикл сложностью O(n), а можно преобразовать выражение, ведь оно представляет собой сумму членов геометрической прогрессии: $4+4^2+4^3+...+4^N=\dfrac{4\cdot(4^N-1)}{4-1}=\dfrac{4\cdot(4^N-1)}{3}$. Тогда сложность алгоритма составит O(1), если не считать операцию возведения в степень.

Программа:

print((4*(4**(int(input()))-1))//3)