10893. Calculator

Ilya’s calculator performs two actions: multiplies the current number by three and adds one to it. The calculator now shows the number 1. Help Ilya to determine the smallest number of operations, after which he will get the number n.

Input. One integer n (10 ≤ n ≤ 10⁹).

Output. Print the minimum number of operations.

Sample input	Sample output
1447	16

SOLUTION

greedy

Algorithm analysis

Greedily move from n to 1:

· if n is divisible by 3, divided it by 3;

· otherwise subtract 1 from n;

Example

Let n = 21. To obtain 1 in the fewest number of operations (four operations), you can do the following:

21 → 7 → 6 → 2 → 1

Algorithm realization

Read the input value of n.

scanf("%d", &n);

Count the number of performed operations in the variable cnt.

cnt = 0;

Greedily move from n to 1.

while (n > 1)

{

if (n % 3 == 0) n /= 3;

else n--;

cnt++;

}

Print the answer.

printf("%d\n", cnt);

Python realization

Read the input value of n.

n = int(input())

Count the number of performed operations in the variable cnt.

cnt = 0

Greedily move from n to 1.

while n > 1:

if n % 3 == 0:

n //= 3

else:

n -= 1

cnt += 1

Print the answer.

print(cnt)