e-olymp 8538. Калькулятор

Условие

Калькулятор Ильи выполняет два действия: умножает текущее число на три и прибавляет к нему единицу. На калькуляторе сейчас число $1$. Помогите Илье определить наименьшее количество действий, после которой он получит число $n$.

Входные данные

Одно число $n$ $\left(10\leq n\leq 10^9\right)$.

Выходные данные

Выведите наименьшее количество операций.

Тесты

Входные данные Выходные данные
1 1447 16
2 18 3
3 111 6

Код программы

Решение

Решим данную задачу от обратного. А именно, пусть нам дано число $n$ и нам надо из него получить $1$, задействовав как можно меньше операций. Для этого объявим цикл while(), который будет работать до тех пор, пока наше число $n$ не будет равно $1$. Стоит заметить, что наименьшее число операций будет тогда и только тогда, когда изначальное число постоянно будет делиться на $3$ без остатка. Примером таких чисел является $3^a$, где $a$ принимает значения $\left(1; +\infty \right)$. Значит, основной упор мы будем делать на работу с делением числа на $3$, чтоб как можно скорее добраться до $1$. Для начала, стоит проверить, делится ли число $n$ нацело на $3$. Если число имеет остаток при делении, то мы отнимаем от него $1$ и проверяем еще раз. В конце концов, мы получаем $1$, но в ответе задачи нам надо вывести количество задействованных операций. Для этого, в самом начале объявляем переменную $k$, которая будет счетчиком. Она будет увеличиваться каждый раз на $1$ после того, как сработает одно из наших условий.

One thought on “e-olymp 8538. Калькулятор

  1. Нет, так эту задачу решать нельзя. Т.е. решать можно, но такое решение я не зачту.
    Попробую намекнуть, что тут не так. Представьте что у вас есть число 0. И вы умеете прибавлять 2 к любому числу. Теперь вас спрашивают, можно ли прибавлением двух постепенно получить $10^100$? И вы, что начнете отнимать два пока до нуля не дойдете? Жизни хватит?

Добавить комментарий