Задание
Над целым числом можно производить следующие операции:
- Если число делится на 3, то делить его на 3;
- Если число делится на 2, то делить его на 2;
- Вычитать 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 |
Код
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
import java.util.*; import java.lang.*; import java.io.*; public class Main { int[] x = new int[1000001]; public int operations(int n) { x[1] = 0; for (int i = 2; i <= n; i++) { x[i] = x[i-1] + 1; if (i%2 == 0) { x[i] = Math.min(x[i], x[i/2] + 1); } if (i%3 == 0) { x[i] = Math.min(x[i], x[i/3] + 1); } } return x[n]; } public static void main (String[] args) { Scanner in = new Scanner(System.in); Main x = new Main(); while (in.hasNextInt()) { int n = in.nextInt(); System.out.println(x.operations(n)); } } } |
Решение
Заведём массив на максимальное количество элементов. x[1] всегда будет равен 0, так как чтобы добраться от единицы к единице нужно 0 шагов. Затем, начиная со второго элемента, пробежимся по всему массиву до [latex]n[/latex], присваивая элементам значения предыдущих элементов, добавляя к ним единицу. Теперь остается выбрать минимум из самого элемента или элемента являющегося результатом деления(на 2 или на 3) с прибавлением единицы.
