Algoritmos e Estruturas de Dados

Transformação de Números

Emil tem um número x e quer transformá-lo noutro número y. Para isso, pode realizar as seguintes operações:
  1. Incrementar o número atual x em 1 (x = x + 1), pagando 1 unidade de dinheiro.
  1. Reduzir o número atual x em 1 (se x for maior que 0) (x = x - 1), pagando 1 unidade de dinheiro.
  1. Multiplicar x por qualquer inteiro positivo k (x = k ⋅ x), pagando 2k unidades de dinheiro.
  1. Dividir x por qualquer inteiro positivo k (se x for divisível por k) (x = x / k), pagando 2k unidades de dinheiro.
Escreva um programa para determinar a menor quantia de dinheiro necessária para transformar x em y. É preciso também imprimir as operações na ordem em que devem ser realizadas. Caso existam várias formas de obter esse custo mínimo, pode apresentar qualquer uma delas. Além disso, não é obrigatório minimizar o número de operações.

Entrada

A entrada consiste em dois inteiros x e y (1 ≤ x, y ≤ 10 000), que representam o número inicial de Emil e o número desejado.

Saída

A primeira linha da saída deve conter dois inteiros separados por espaço, m e n, que representam o número de operações e a quantia mínima de dinheiro necessária para transformar x em y.
Nas m linhas seguintes, imprima o índice da operação, , na ordem em que devem ser realizadas. Se a operação for Multiplicar ou Dividir ( ou ), imprima o índice da operação seguido de um espaço e do número .

Exemplos

Entrada
Saída
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