Производители хлопьев Алфавит выпустили новую линейку - вопрос №13582844 от маря39 22.04.2020 13:55

Question

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

маря39 · Answer

Алгоритм: на каждой позиции может быть одна из четырёх букв. Значит, если слово состоит из 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)