Transformación de Números
Emil tiene un número
x y quiere convertirlo en otro número y. Para lograrlo, puede realizar las siguientes operaciones:- Emil puede incrementar el número actual
xen1(x = x + 1) y pagar 1 unidad de dinero por ello.
- Emil puede decrementar el número actual
xen1(si x es mayor que 0) (x = x - 1) y pagar 1 unidad de dinero por ello.
- Emil puede multiplicar
xpor cualquier entero positivok(x = k ⋅ x) y pagar 2k unidades de dinero por ello.
- Emil puede dividir
xentre cualquier entero positivoksixes divisible pork(x = x / k) y pagar 2k unidades de dinero por ello.
Escribe un programa que determine la menor cantidad de dinero que Emil necesita para transformar
x en y. También debes mostrar las operaciones en el orden en el que deben ser realizadas. Ten en cuenta que, si hay varias maneras de conseguir el mínimo costo, se puede devolver cualquiera de ellas. Además, no es necesario minimizar la cantidad de operaciones.Entrada
La entrada está compuesta por dos enteros
x y y (1 ≤ x, y ≤ 10 000), que representan el número inicial de Emil y el número deseado.Salida
La primera línea de la salida debe contener dos enteros separados por un espacio,
m y n, que indican el número de operaciones y la cantidad mínima de dinero que Emil necesita para transformar x en y.En las siguientes
m líneas, muestra el índice de la operación, , en el orden en que se deben ejecutar. Si la operación es Multiplicar o Dividir ( o ), imprime el índice de la operación seguido de un espacio y el número .Ejemplos
Entrada | Salida |
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