Задача C. Крестьянин и чёрт

Автор:Гребенюк Н.С., русский фольклор   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Встретил крестьянин чёрта, и тот говорит ему: «Видишь мост через эту реку? Стоит тебе только перейти через этот мост — у тебя будет втрое больше денег, чем есть. Перейдёшь назад, опять станет втрое больше, чем было. И так каждый раз, как ты будешь переходить через мост».

 — Ой ли? — говорит крестьянин.

 — Верное слово! — уверяет чёрт. — Только чур, уговор! За то, что я тебе утраиваю деньги, ты, каждый раз перейдя через мост, будешь отдавать мне по X копеек. Иначе не согласен.

 — Ну, что же, это не беда! — говорит крестьянин. — Раз деньги будут утраиваться, так отчего же тебе X копеек каждый раз не дать?

Перешёл крестьянин через мост, посчитал деньги — и вправду, стало втрое больше, чем было. Отсчитал X копеек, бросил чёрту, перешёл снова.. После N-го перехода по мосту отсчитал крестьянин в N-й раз X копеек, бросил чёрту и понял, что не осталось у него ни копейки.

Сколько копеек было у крестьянина изначально?

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

Формат входных данных

В первой строке ввода содержится целое число X — количество копеек, которые крестьянин будет отдавать чёрту.

Во второй строке содержится целое число N — сколько раз крестьянин смог пройти по мосту, прежде чем у него закончились копейки.

Формат выходных данных

Выведите единственное целое число K — изначальное количество копеек у крестьянина.

Ограничения

1 ≤ X ≤ 109

1 ≤ N ≤ 18

Описание системы оценивания

Баллы начисляются пропорционально количеству пройденных тестов.

По запросу сообщается количество набранных баллов.

Пояснения к примерам

В первом примере у крестьянина изначально было 5 копеек. После перехода по мосту копеек стало 15 и крестьянину пришлось их все отдать чёрту.

Примеры тестов

Стандартный вход Стандартный выход
1
15
1
5
2
81
4
40

Разбор

Полное решение

Проще всего начинать решать задачу с конца.

После последнего, N-го перехода, у крестьянина стало 0 копеек. Перед этим он отдал свои последние X копеек черту, а до перехода по мосту их было в три раза меньше, т.е. X3.

Значит, после (N − 1)-го перехода (и до N-го) он имел X3 копеек, перед этим он отдал X копеек черту (было X3 + X), а до этого их количество утроилось, т.е. было X3 + X3 копеек (после (N − 2)-го и до (N − 1)-го перехода).

Уже можно увидеть закономерность: каждый раз мы прибавляем X и делим на 3.

Обозначив ai как количество копеек после i-го перехода, получим следующую формулу: ai = ai + 1 + X3. По условию aN = 0, проведя N итераций (от i = N − 1 до i = 0) получим изначальное количество копеек в a0 (после условного "нулевого" перехода и до первого перехода). Асимптотика такого решения O(N).

К аналогичной рекурсивной формуле можно было прийти, составив прямую формулу из условия (ai + 1 = ai ⋅ 3 − X) и выразив из неё ai.

Также исходя из закономерности можно разложить a0 в виде: a0 = a1 + X3 = a2 + X3 + X3 = ..  + X3 + X3 = X3 + X32 + ..  + X3N

Частичные решения

Ответ можно перебирать напрямую, проверяя, станет ли выбранное число i равно X после N указанных в условии операций над ним. Сложность такого алгоритма составит O(N ⋅ X), что не укладывается в указанное ограничение по времени при больших N.


0.072s 0.011s 13