Задача №2918. Числа-подстроки
За один шаг к числу X разрешается прибавить или из числа X разрешается вычесть любое положительное число Y, десятичная запись которого является подстрокой десятичной записи числа X. Стоимость такой операции равна сумме цифр числа Y.
Необходимо за минимальную стоимость получить из числа a число b, при этом все промежуточные числа должны быть положительными и не должны превышать n.
Входной файл содержит три целых числа: n, a, b (1 ≤ a, b ≤ n ≤ 5000).
Если из числа a нельзя получить число b, выведите в выходной файл одно число -1.
Если такая последовательность преобразований существует, в первой строке выходного файла выведите минимальную стоимость требуемого преобразования. Во второй строке выходного файла выведите число k — количество шагов в преобразовании. В последующих k строках выведите сами шаги преобразования по одному в строке. Каждая строка должна иметь вид +число или –число, в зависимости от того, прибавляется или вычитается очередное число.
20 12 18
5 3 -2 +10 -2
100 5 43
29 8 +5 +1 +1 +1 +13 +26 -5 -4
50 5 43
-1