Задача взята с сайта e-olymp
Задача
Однажды царь наградил крестьянина яблоком из своего сада. Пошёл крестьянин к саду и видит: весь сад огорожен $n$ заборами, в каждом заборе только одни ворота, и в каждых воротах стоит сторож. Подошёл крестьянин к первому сторожу и показал царский указ, а сторож ему в ответ: «Иди возьми, но при выходе отдашь мне половину тех яблок, что несёшь, и ещё одно». То же ему сказали и второй, и третий сторож и т.д. Сколько яблок должен взять крестьянин, чтобы после расплаты со сторожами у него осталось одно яблоко?
Входные данные
Количество заборов $n (1 \leqslant n \leqslant 62)$ в саду.
Выходные данные
Вывести количество яблок, которое должен взять крестьянин, чтобы после расплаты со сторожами у него осталось одно яблоко.
Тесты
| # |
ВХОДНЫЕ ДАННЫЕ |
ВЫХОДНЫЕ ДАННЫЕ |
| 1 |
1 |
4 |
| 2 |
3 |
22 |
| 3 |
30 |
50331646 |
| 4 |
60 |
3458764513820540926 |
| 5 |
62 |
13835058055282163710 |
Решение
Циклы
Последовательность необходимых количеств яблок задается формулой $x_{n+1}=2 \cdot (x_{n}+1);x_{1}=1.$ Мы можем поочередно вычислять элементы последовательности через цикл.
|
|
#include <iostream> int main() { int n; std::cin>>n; unsigned long long k = 1; for(int i = 0; i<n; i++)k = (k + 1) * 2; std::cout<<k; } |
Линейное решение
Преобразуем исходное выражение для $x_{n+1}=2 \cdot x_{n}+2.$ Можно видеть, что каждая следующая итерация увеличивает степень всех двоек входящих в предыдущую на 1 и добавляет 2. Выпишем формулу для $x_{n+m}=2^{m}x_n+2^{m-1}x_n+\cdots+2.$ Можно увидеть, что $x_{n+m}$ содержит слагаемое $2^{m}x$, а так же сумму слагаемых вида $\displaystyle \sum_{i=1}^{m}2^i \displaystyle.$ Если учесть, что $x_{1}=1$, то $\displaystyle x_n=2^{n}+ \sum_{i=1}^{n}2^i \displaystyle=2^{n+1}+2^n-2=2^{n}\cdot(2+1) -2.$ Следовательно формула $n$-го члена — [latex]x_n=3\cdot 2^n-2.[/latex]
|
|
#include <iostream> int main() { int n; std::cin>>n; unsigned long long t = 2; std::cout<<3*(t<<n-1)-2; } |
Решения на ideone
Related Images:
