Условие
Калькулятор Ильи выполняет два действия: умножает текущее число на три и прибавляет к нему единицу. На калькуляторе сейчас число $1$. Помогите Илье определить наименьшее количество действий, после которой он получит число $n$.
Входные данные
Одно число $n$ $\left(10\leq n\leq 10^9\right)$.
Выходные данные
Выведите наименьшее количество операций.
Тесты
| № | Входные данные | Выходные данные |
| 1 | 1447 | 16 |
| 2 | 18 | 3 |
| 3 | 111 | 6 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
#include <iostream> using namespace std; int main() { long long n; int k = 0; cin >> n; while (n > 0) { k += n%3 + 1; n /= 3; } cout << k - 2; } |
Решение
Решим данную задачу от обратного. Пусть нам дано число $n$ и нам надо из него получить $1$, задействовав как можно меньше операций. Для этого объявим цикл while(), который будет работать до тех пор, пока наше число $n$ будет строго больше $0$. Внутри цикла опишем следующее решение: пусть k будет счётчиком нажатий на кнопки калькулятора и изначально равняется $0$. Тогда, при каждом шаге цикла мы к счётчику будем прибавлять остаток от деления на $3$. n%3 — именно столько раз нам потребуется отнять $1$ от $n$ чтобы можно было нацело разделить на $3$. Далее, делим $n$ на $3$ и это потребует еще одного нажатия (что и происходит в строке $9$). Так как в условии цикла мы написали, что $n > 0$, то мы пройдём лишнюю итерацию и к счётчику прибавятся два лишних шага. Поэтому, при выводе ответа, от $k$ отнимаем $2$.