Trasformazione di un Numero
Emil ha un numero
x e desidera trasformarlo in un altro numero y. Per riuscirci, può eseguire le seguenti operazioni:- Emil può incrementare il numero corrente
xdi1(x = x + 1) pagando 1 unità di denaro.
- Emil può decrementare il numero corrente
xdi1(se x è maggiore di 0) (x = x - 1) pagando 1 unità di denaro.
- Emil può moltiplicare
xper qualsiasi intero positivok(x = k ⋅ x) pagando 2k unità di denaro.
- Emil può dividere
xper qualsiasi intero positivok, sexè divisibile perk(x = x / k), pagando 2k unità di denaro.
Scrivi un programma che determini la quantità minima di denaro necessaria a Emil per trasformare
x in y. Devi anche elencare le operazioni nell’ordine in cui vanno eseguite. Tieni presente che, in caso esistano più soluzioni con lo stesso costo minimo, puoi scegliere liberamente quale mostrare. Inoltre, non è obbligatorio minimizzare il numero di operazioni.Input
L’input è composto da due interi
x e y (1 ≤ x, y ≤ 10 000), che rappresentano rispettivamente il numero iniziale di Emil e quello desiderato.Output
La prima riga dell’output deve contenere due interi separati da uno spazio,
m e n, dove m è il numero di operazioni e n è il costo minimo in unità di denaro per trasformare x in y.Nelle successive
m righe, stampa l’indice dell’operazione, , nell’ordine in cui deve essere eseguita. Se l’operazione è di tipo Moltiplica o Dividi ( o ), stampa l’indice seguito da uno spazio e dal numero .Examples
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