Условие
У Ибрагима есть магическая чёрная шайтан-машинка. На ней есть три кнопки и табло. Табло может показывать не более чем четырёхзначные числа. Каждая из кнопок меняет число некоторым образом: первая домножает его на [latex]3[/latex], вторая прибавляет к нему сумму его цифр, а третья вычитает из него [latex]2[/latex]. В случае, если число становится отрицательным или превосходит [latex]9999[/latex], шайтан-машинка ломается.
Ибрагим может нажимать кнопки в любом порядке. Его интересует, как ему получить на табло число [latex]b[/latex] после некоторой последовательности нажатий, если сейчас шайтан-машинка показывает [latex]a[/latex]. Помогите ему найти минимальное необходимое число нажатий.
Входные данные
В одной строке находится два натуральных числа [latex]a[/latex] и [latex]b[/latex] latex[/latex].
Выходные данные
Вывести минимальное необходимое количество действий.
Код
|
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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <iostream> using namespace std; int sum_n (int n){ //подсчёт суммы цифер в числе int res = n/1000 + (n%1000-n%100)/100 + (n%100-n%10)/10 + n%10; return res; } bool was [10000]; //массив использованных вершин. int vertex[10000]; //подсчёт кол-ва пройденных рёбер.. queue<int> q; //очередь для BFS //BFS void bfs (int start, int finish){ if (start==finish){ //если мы сразу попали в нужную вершину - выходим из программы. cout << 0 << endl; return; } else { for (int i=0; i<10000; i++){ //предположим, что расстояние до любой вершины = 1 vertex[i]=1; } q.push (start); //будем рассматривать каждую вершину was[start] = true; while (!q.empty()){ int tmp = q.front(); //рассматриваемая вершина q.pop(); int tmp1 = tmp; tmp1 *= 3; //"ребёнок" рассматриваемой вершины, со значением родителбской вершины *3. if (!was[tmp1]){ if (tmp1 == finish){//если финиш, то выводим длину пути до вершины. cout << vertex[tmp] << endl; return; } else if (tmp1 < 10000 && tmp1>=0){ was[tmp1] = true;//иначе помечаем вершину, как пройденную и засовываем её в очередь на рассмотрение q.push(tmp1); vertex[tmp1]=vertex[tmp]+1;//и прибавляем 1 к длине пути. } } //действия повторяются для других операций. tmp1=tmp; tmp1 += sum_n(tmp1); if (!was[tmp1]){ if (tmp1 == finish){ cout << vertex[tmp] << endl; return; } else if (tmp1 < 10000 && tmp1>=0){ was[tmp1] = true; vertex[tmp1]=vertex[tmp]+1; q.push(tmp1); } } tmp1=tmp; tmp1 -= 2; if (!was[tmp1]){ if (tmp1 == finish){ cout << vertex[tmp] << endl; return; } else if (tmp1 < 10000 && tmp1>=0){ was[tmp1] = true; vertex[tmp1]=vertex[tmp]+1; q.push(tmp1); } } } } } int main() { int a, b; cin >> a >> b; //ввод начала и конца bfs (a, b);//процедура выполнения return 0; } |
Код на Java:
|
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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
import java.util.*; import java.lang.*; import java.io.*; class ShaitanEngines { private static int N = 10001; private static boolean [] was = new boolean [N]; private static int [] vertice = new int [N]; private static Queue <Integer> q = new LinkedList(); public static int sum (int n) { return (n/1000 + (n%1000-n%100)/100 + (n%100-n%10)/10 + n%10); } public static void bfs (int start, int finish) { if (start == finish) { System.out.println(1); return; } else { for (int i=0; i<N; i++){ //предположим, что расстояние до любой вершины = 1 vertice[i]=1; } q.add (start); //будем рассматривать каждую вершину was[start] = true; while (!q.isEmpty()){ int tmp = q.element(); //рассматриваемая вершина q.remove(); int tmp1 = tmp; tmp1 *= 3; //"ребёнок" рассматриваемой вершины, со значением родителбской вершины *3. if (!was[tmp1]){ if (tmp1 == finish){//если финиш, то выводим длину пути до вершины. System.out.println(vertice[tmp]); return; } else if (tmp1 < 10000 && tmp1>=0){ was[tmp1] = true;//иначе помечаем вершину, как пройденную и засовываем её в очередь на рассмотрение q.add(tmp1); vertice[tmp1]=vertice[tmp]+1;//и прибавляем 1 к длине пути. } } //действия повторяются для других операций. tmp1=tmp; tmp1 += sum(tmp1); if (!was[tmp1]){ if (tmp1 == finish){ System.out.println(vertice[tmp]); return; } else if (tmp1 < 10000 && tmp1>=0){ was[tmp1] = true; vertice[tmp1]=vertice[tmp]+1; q.add(tmp1); } } tmp1=tmp; tmp1 -= 2; if (!was[tmp1]){ if (tmp1 == finish){ System.out.println(vertice[tmp]); return; } else if (tmp1 < 10000 && tmp1>=0){ was[tmp1] = true; vertice[tmp1]=vertice[tmp]+1; q.add(tmp1); } } } } } public static void main (String[] args) { Scanner sc = new Scanner (System.in); int a = sc.nextInt(); int b = sc.nextInt(); bfs(a, b); } } |
Решение
Для решения данной задачи я решил использовать алгоритм BFS (поиск в ширину). Обычно, данный алгоритм применяется для поиска пути от одной вершины к другой, причём длина пути должна быть минимальной.
Всю «карту» расположения операций можно представить в виде графа-дерева, где от каждой вершины отходят максимум 3 ребра (в каждой вершине по операции, проделанной со значением вершины, которая находится на уровень выше). Будем рассматривать каждую вершину. Если исходная вершина и есть конечной, то выходим из программы с вердиктом «0». Иначе будем поочерёдно рассматривать все вершины. Заведём массив расстояний, в котором предположим, что расстояние до нужной нам вершины равно 1. С проходом каждой вершины будем подсчитывать расстояние до нужной нам вершины (прибавляя к расстоянию 1), в которую мы рано или поздно попадём.
Принято. Единственное замечание — магическая константа 1000. В программе число 1000 может встречаться в различных смыслах. При необходимости внесения изменений приходится разбираться какая 1000, что означает. Чтобы этого избежать используются именованные константы.