2060. Сказка о яблоке

Однажды царь наградил крестьянина яблоком из своего сада. Пошёл крестьянин к саду и видит: весь сад огорожен n заборами, в каждом заборе только одни ворота, и в каждых воротах стоит сторож. Подошёл крестьянин к первому сторожу и показал царский указ, а сторож ему в ответ: "Иди возьми, но при выходе отдашь мне половину тех яблок, что несёшь, и ещё одно". То же ему сказали и второй, и третий сторож и т.д. Сколько яблок должен взять крестьянин, чтобы после расплаты со сторожами у него осталось одно яблоко?

Вход. Количество заборов n (1 ≤ n ≤ 62) в саду.

Выход. Вывести количество яблок, которое должен взять крестьянин, чтобы после расплаты со сторожами у него осталось одно яблоко.

Пример входа	Пример выхода
1	4

РЕШЕНИЕ

математика

Анализ алгоритма

Пусть после прохода через очередные ворота у крестьянина останется k яблок. Значит до прохода через ворота у него должно было быть (k + 1) * 2 яблок. Повторяя эту процедуру n раз, мы найдем начальное количество яблок у крестьянина.

При n = 62 ответом будет число, которое не помещается в тип данных long long. Зато помещается в unsigned long long.

Пример

В конце у крестьянина было 1 яблоко. Если ворота считать с конца, то:

перед 1-ыми воротами было (1 + 1) * 2 = 4 яблока;

перед 2-ыми воротами было (4 + 1) * 2 = 10 яблок;

перед 3-ими воротами было (10 + 1) * 2 = 22 яблока;

перед 4-ими воротами было (22 + 1) * 2 = 46 яблок;

Реализация алгоритма

Читаем значение n.

scanf("%d",&n);

Вычисляем начальное количество яблок у крестьянина.

res = 1;

for(i = 0; i < n; i++)

res = 2 * (res + 1);

Выводим ответ.

printf("%llu\n",res);