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

Условие

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

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

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

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ X ≤ 10⁹

1 ≤ N ≤ 18

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

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

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

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

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

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

15
1

5

81
4

40

Разбор

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

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

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

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

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

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

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

Также исходя из закономерности можно разложить a₀ в виде: a₀ = a₁ + X3 = a₂ + X3 + X3 = ..  + X3 + X3 = X3 + X3² + ..  + X3^N

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

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