数値の変換
Emil は数値
x を持っており、これを別の数値 y に変換したいと考えています。 そのために、Emil は以下の操作を行うことができます:- 現在の数
xを 1 増やし (x = x + 1)、その代わりに 1 ユニットのお金を支払う。
- 現在の数
xを (x が 0 より大きい場合) 1 減らし (x = x - 1)、その代わりに 1 ユニットのお金を支払う。
- 現在の数
xに対して、任意の正の整数kを掛ける (x = k ⋅ x)、その代わりに 2k ユニットのお金を支払う。
- 現在の数
xがkで割り切れるとき、任意の正の整数kで割る (x = x / k)、その代わりに 2k ユニットのお金を支払う。
このとき、
x を y に変換するのに必要な最小の費用がいくらになるかを求め、そのときに行う操作の順番を出力するプログラムを作成してください。最小費用を達成できる方法が複数ある場合は、そのうちのどれを出力しても構いません。また、操作の回数を最小化する必要はありません。入力
入力は2つの整数
x と y (1 ≤ x, y ≤ 10 000) からなり、これはそれぞれ Emil の初期値と目標値を表しています。出力
出力の最初の行には、操作の回数
m と、x を y に変換するために必要な最小の費用 n を空白区切りで出力してください。続く
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