Transformation de nombres
Emil dispose d’un nombre
x et souhaite le transformer en un autre nombre y. Pour atteindre cet objectif, il peut effectuer les opérations suivantes :- Il peut augmenter le nombre
xde1(x = x + 1) en payant 1 unité de monnaie.
- Il peut diminuer le nombre
xde1(sixest plus grand que 0) (x = x - 1) en payant 1 unité de monnaie.
- Il peut multiplier
xpar un entier positifk(x = k ⋅ x) en payant 2k unités de monnaie.
- Il peut diviser
xpar un entier positifksixest divisible park(x = x / k) en payant 2k unités de monnaie.
Écrivez un programme pour déterminer le montant minimal d’argent dont Emil a besoin pour transformer
x en y. Vous devrez également afficher les opérations dans l'ordre où elles doivent être effectuées. Notez que s’il existe plusieurs façons d’atteindre ce coût minimal, vous pouvez en afficher n’importe laquelle. Par ailleurs, il n’est pas nécessaire de réduire au minimum le nombre d’opérations.Entrée
L’entrée se compose de deux entiers
x et y (1 ≤ x, y ≤ 10 000), qui représentent respectivement le nombre initial d’Emil et le nombre souhaité.Sortie
La première ligne de la sortie doit afficher deux entiers séparés par un espace :
m et n, où m désigne le nombre d’opérations et n correspond au montant minimal d’argent nécessaire pour transformer x en y.Sur les
m lignes suivantes, indiquez l’indice de l’opération, , dans l’ordre où elles doivent être exécutées. Si l’opération est une multiplication ou une division ( ou ), inscrivez d’abord l’indice de l’opération , suivi d’un espace, puis le nombre .Exemples
Input | Output |
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