Если k = 1, то ответ на задачу, очевидно,
, в противном случае будем жадно уменьшать количество файлов жадно.
В каждый момент времени мы можем находиться в одной из трёх ситуаций:
- Если n < k, то нам ничего не остается, кроме как n - 1 раз уменьшить число за A, мы можем сделать это за
формулой. - Если n > k и n не кратно k, то нам ничего не остается, кроме как
уменьшить число за A, эту часть тоже можно сделать за
формулой. - Если n кратно k, то нам всегда выгодно сделать переход к
за
. Если
корректность очевидна. Иначе предположим мы не сделали переход к
сейчас, а сделали его на отрезке
из числа
, тогда мы заплатили
. Это
или
, что не выгоднее перехода сразу к
и последующему спуску к числу
. Данный переход тоже делается за
.
Поскольку в каждой ситуации мы можем побывать не более
раз асимптотика решения
.