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+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]

Решения на ideone

Related Images:

7 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$ нет необходимости брать в скобки.
  1. Вы почему-то не исправляете ошибок. Скопирую основные замечания:

    • Пожалуйста, оформите в ТеХ всё неравенство, а не отдельные буквы.
    • Умножение в математических формулах не обозначают звёздочкой.
    • Если нужен дефис, не ставьте вокруг него пробелов — получается тире.
    • В первом коде, не используйте функцию возведения в действительную степень. Для получения степени двойки следует использовать операцию битового сдвига влево.
    • По какой-то причине откатилась публикация, все вернул.

    • Наша CMS запоминает все опубликованные версии. И даже выполняет автосохранение. С откатом публикаций проблем возникать не должно.
      Хотя, поломаться могло всё что угодно.

  2. Я позволил себе кое-что поправить чтобы сократить путь к готовой работе. Если какой-то момент был принципиальным, пишите — будем разбираться.
    За Вами остается только поправить эту формулу $x_{n+m}=2^{m}x_ n+2_x^{m-1}+\cdots+2.$

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