Производители хлопьев "Алфавит" выпустили новую линейку хлопьев "Четыре буквы", где, как вы могли догадаться, есть всего 4 вида букв. Ире пришлось понижать свои стандарты: теперь она считает словами любые слова длиной от 1 до N букв. Сколько слов она сможет составить на этот раз? python
More Questions From This User See All
Answers & Comments
Verified answer
Алгоритм: на каждой позиции может быть одна из четырёх букв. Значит, если слово состоит из k букв, то количество слов ровно 4^k, Значит, всего слов 4 + 4² + 4³ + ... + 4ⁿ. Можно реализовать цикл сложностью O(n), а можно преобразовать выражение, ведь оно представляет собой сумму членов геометрической прогрессии:
. Тогда сложность алгоритма составит O(1), если не считать операцию возведения в степень.
Программа:
print((4*(4**(int(input()))-1))//3)