Задача взята с сайта 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.$ Мы можем поочередно вычислять элементы последовательности через цикл.
|
1 2 3 4 5 6 7 8 |
#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]
|
1 2 3 4 5 6 7 |
#include <iostream> int main() { int n; std::cin>>n; unsigned long long t = 2; std::cout<<3*(t<<n-1)-2; } |
Я исправил, но, Игорь Евгеньевич, Вы ,кажется, слишком увлеклись увеличением объема вашего комментария:
64-битный long long содержит в себе числа от $-2^{63}$ до +$2^{63}$ В задаче же максимальное число — $3\cdot2^{63}$ , что однозначно превышает $2^{63}$.
«Уберите концовку от слов «Решения на e-olymp» и дальше. Ваш код на этом сайте видите только Вы» — Убрал, но возможно Вы это и другим ребятам скажете?А то я у каждого в публикации увидел ссылку на засчитанное решение на e-olymp.Можно ли узнать в чем конкретно моя проблема?
Что же касается увлечений, то они у меня другие :).
Теперь замечания. Увы, снова несколько.
Вы почему-то не исправляете ошибок. Скопирую основные замечания:
По какой-то причине откатилась публикация, все вернул.
Наша CMS запоминает все опубликованные версии. И даже выполняет автосохранение. С откатом публикаций проблем возникать не должно.
Хотя, поломаться могло всё что угодно.
Я позволил себе кое-что поправить чтобы сократить путь к готовой работе. Если какой-то момент был принципиальным, пишите — будем разбираться.
За Вами остается только поправить эту формулу $x_{n+m}=2^{m}x_ n+2_x^{m-1}+\cdots+2.$