e-olymp 1560. Уменьшающееся число

Задание

Над целым числом можно производить следующие операции:

  1. Если число делится на 3, то делить его на 3;
  2. Если число делится на 2, то делить его на 2;
  3. Вычитать 1.

По заданному натуральному числу [latex]n[/latex] найти наименьшее количество операций, после выполнения которых получится 1.

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

Каждая строка содержит одно натуральное число [latex] n(1 ≤ n ≤ 10^{6})[/latex].

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

Для каждого значения [latex]n[/latex] в отдельной строке вывести наименьшее количество операций, после выполнения которых получится 1.

Тесты

Ввод Вывод
1
5
10
0
3
3
12
7
21
3
3
4
256
1037
8771
9022
102651
8
11
13
13
19

Код

Решение

Заведём массив на максимальное количество элементов. x[1] всегда будет равен 0, так как чтобы добраться от единицы к единице нужно 0 шагов. Затем, начиная со второго элемента, пробежимся по всему массиву до [latex]n[/latex], присваивая элементам значения предыдущих элементов, добавляя к ним единицу. Теперь остается выбрать минимум из самого элемента или элемента являющегося результатом деления(на 2 или на 3) с прибавлением единицы.

Ссылки

1.Код на Ideone
2.Условие на e-olymp

2 thoughts on “e-olymp 1560. Уменьшающееся число

  1. — Опять путаете где код, а где формула. Смотрите, вот формула: $x_1$, а вот код: x[1]. Ну, и как их можно перепутать 🙂
    — Меток нет, категории и той нет. Я даже не знаю, куда это зачислять.

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

Ваш e-mail не будет опубликован. Обязательные поля помечены *