Алгоритмы и структуры данных

Преобразование числа

У Эмиля есть число x, и он хочет превратить его в другое число y. Для этого он может выполнять следующие операции:
  1. Увеличить текущее число x на 1 (x = x + 1) и заплатить 1 денежную единицу.
  1. Уменьшить текущее число x на 1 (если x больше 0) (x = x - 1) и заплатить 1 денежную единицу.
  1. Умножить x на любое положительное целое число k (x = k ⋅ x), заплатив 2k денежных единиц.
  1. Поделить x на любое положительное целое число k (если x делится на k), (x = x / k) и заплатить 2k денежных единиц.
Напишите программу, которая вычислит минимальную сумму денег, необходимую Эмилю, чтобы превратить x в y. Кроме того, выведите последовательность операций в том порядке, в котором их нужно выполнить. Если существует несколько способов достичь минимальной стоимости, вы можете вывести любой из них. При этом не обязательно стремиться к минимальному количеству операций.

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

Вход содержит два целых числа x и y (1 ≤ x, y ≤ 10 000), которые задают начальное число Эмиля и желаемое число.

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

В первой строке нужно вывести два числа через пробел: m и n, где m — количество операций, а n — минимальная сумма денег, необходимая для преобразования x в y.
В следующих m строках выведите индекс операции по порядку выполнения. Если операция — это Multiply (умножение) или Divide (деление) (то есть или ), следует вывести индекс операции и через пробел число .

Примеры

Входные данные
Выходные данные
3 7
4 4 1 1 1 1
10 21
2 5 3 2 1
21 10
2 5 2 4 2
10 32
3 8 3 3 1 1

Constraints

Time limit: 5 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue