Задача Remake. Рассмотрим 7-значные целые числа в десятичной системе счисления, разрешая нули в старших разрядах. То есть, числа от 0000000 до 9999999. Над числом разрешено выполнять такие преобразования:
– прибавить 1 (не применимо к 9999999);
– вычесть 1 (не применимо к 0000000);
– умножить на любое натуральное число k от 2 до 9(применимо только, если полученное произведение не превышает 9999999);
– разделить на любое натуральное число k от 2 до 9(применимо только, если число до преобразования кратноk);
– выполнить циклический сдвиг влево, то есть стереть цифру самого старшего разряда и дописать ее справа (например, 1234567 → 2345671; применимо к любому числу);
– выполнить циклический сдвиг вправо, т.е. стереть цифру самого младшего разряда и дописать ее слева (например, 1234567 → 7123456; применимо к любому числу).
Напишите программу, которая по двум указанным 7-значным числам A и B находит, как превратить первое во второе за минимальное количество шагов.
Технические условия. Программа Remake считывает с клавиатуры (устройства стандартного ввода) начальное и конечное значение A и B. Каждое значение состоит ровно из7-ми десятичных цифр, между значениями находится ровно один пробел.
Программа выводит на экран (устройство стандартного вывода) сначала минимальное количество преобразованийM, далее следует вывести M+1 штук 7-значных чисел, где первое равно A, последнее равно B, и каждое следующее получено из предыдущего одним из преобразований. Числа, меньшие 106, должны быть дополнены нулями до 7-значных. Если возможны различные правильные последовательности с одинаковым минимальным количеством преобразований – выводите любую одну из них. Числа выводятся через пробел.
Примеры
Ввод
3330333 3333033
Вывод
1 3330333 3333033
Ввод
0000000 0370370
Вывод
6 0000000 0000001 1000000 0999999 0111111 0037037 0370370