e-olymp 2060. Сказка о яблоке.

Задача взята с сайта 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.$ Мы можем поочередно вычислять элементы последовательности через цикл, или воспользоваться линейной формулой  $x_{n}=(3\cdot 2^n)-2.$

Выведение линейной формулы:

Преобразуем исходное выражение: $x_{n+1}=2 \cdot x_{n}+2$. Можно видеть, что каждая следующая итерация увеличивает степень всех двоек входящих в предыдущую на 1 и добавляет 2. Выпишем формулу для номера $n+m:$ $x_{n+m}=2^{m}x_ n+2_x^{m-1}+…+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=2^{n+1}+2^n -2 = 2^{n}\cdot(1+2)-2= 3\cdot 2^n-2.$ Следовательно формула $n$-го члена — $x_n= 3\cdot 2^n-2$.

Решения на ideone

3 thoughts on “e-olymp 2060. Сказка о яблоке.

    • Пожалуйста, оформите в ТеХ всё неравенство, а не отдельные буквы.
    • Умножение в математических формулах не обозначают звёздочкой.
    • Если нужен дефис, не ставьте вокруг него пробелов — получается тире.
    • не «влазит» лучше заменить на «не помещается». И почему он не помещается? Вы же используете 64-битные числа.
    • Пожалуйста, не используйте массивы.
    • Уберите кириллицу из постоянной ссылки на Вашу публикацию.
    • Пожалуйста, проявляйте свою творческую креативность в коде, а не при выборе меток (ключевых слов). Следующий такой «прикол» и Вы потеряете права публикации на сайте.
    • Уберите концовку от слов «Решения на e-olymp» и дальше. Ваш код на этом сайте видите только Вы.
    • Вы не вывели формулу, а только привели её. А как она получилась?
    • В первом коде, не используйте функцию возведения в действительную степень. Для получения степени двойки следует использовать операцию битового сдвига влево.
    • Я исправил, но, Игорь Евгеньевич, Вы ,кажется, слишком увлеклись увеличением объема вашего комментария:

      64-битный long long  содержит в себе числа от $-2^{63}$ до +$2^{63}$ В задаче же максимальное число —  $3\cdot2^{63}$ , что однозначно превышает $2^{63}$.

      «Уберите концовку от слов «Решения на e-olymp» и дальше. Ваш код на этом сайте видите только Вы» — Убрал, но возможно Вы это и другим ребятам скажете?А то я у каждого в публикации увидел ссылку на засчитанное решение на e-olymp.Можно ли узнать в чем конкретно моя проблема?

        • Объём моих комментариев определяет количество обнаруженных недочетов. Если Вы будете настаивать, то я могу делать замечания по одному. Но это очень затянет процесс. Кроме того, за каждый мой комментарий с замечаниями я снимаю один балл. Не думаю, что Вам понравится такой режим.
          Что же касается увлечений, то они у меня другие :).
        • В условии указано, что максимальное значение $n=62.$ При использовании беззнаковых 64-битных целых чисел, Вы можете оперировать значениями от $0$ до $2^{64}-1$. Вот всё и поместится.
        • Я мог у кого-то не заметить этот недостаток. А возможно, у них не было других ссылок на e-olymp.com и всё было вполне логично. Но мне не хотелось бы перепроверять работы. Вы не подскажите, у кого видели похожую ошибку? Или, еще лучше, напишите сами комментарии к их публикациям.
          Теперь замечания. Увы, снова несколько.
        • Первое предложение слишком длинное и запутанное. Лучше избегать объединения больше двух простых предложений в одно сложное.
        • Если формула заканчивается знаком препинания, то лучше внести его в формулу. Иначе точка может оказаться на новой строке, а это не приемлемо.
        • Поставьте пропущенные точки в конце предложений.
        • Пределы суммирования принято ставить над и под знаком сигмы, а не с боку. Найдите способ это сделать. Если не найдёте, оставьте как есть. Но обязательно укажите нижнюю границу суммирования, а не только верхнюю.
        • $2^n$ нет необходимости брать в скобки.

Добавить комментарий