Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 100 点
問題文
正の整数 X, N が与えられる.
最初,黒板に整数 X が書かれている.
JOI 君は,以下の操作を繰り返し行う.
操作: 今,黒板に書かれている数を x とする.x を 3 で割った余りを計算し,r とする.r の値に応じて,黒板に書かれている数を以下のように書き換える.
- r=0 のとき,黒板に書かれている数を,x に 1 を足した数に書き換える.
- r=1 のとき,黒板に書かれている数を,x に 2 を掛けた数に書き換える.
- r=2 のとき,黒板に書かれている数を,x に 3 を掛けた数に書き換える.
黒板に書かれている数が N 以上になるまでに必要な操作の回数を求めよ.
制約
- 1 \leqq X < N \leqq 100\,000.
- 入力される値はすべて整数である.
入力
入力は以下の形式で与えられる.
X N
出力
黒板に書かれている数が N 以上になるまでに必要な操作の回数を出力せよ.
答え以外は何も出力しないこと.(入力を促す文章なども出力しないこと.)
解答形式については,練習問題やその解答例 を参考にしても良い.
入力例 1
2 40
出力例 1
4
最初,黒板に書かれている数は 2 である.
1 回目の操作では,操作の始めに黒板に書かれている数 x は 2 である.x を 3 で割った余り r は 2 であるため,黒板に書かれている数を,x=2 に 3 を掛けた数である 6 に書き換える.
2 回目の操作では,操作の始めに黒板に書かれている数 x は 6 である.x を 3 で割った余り r は 0 であるため,黒板に書かれている数を,x=6 に 1 を足した数である 7 に書き換える.
3 回目の操作では,操作の始めに黒板に書かれている数 x は 7 である.x を 3 で割った余り r は 1 であるため,黒板に書かれている数を,x=7 に 2 を掛けた数である 14 に書き換える.
4 回目の操作では,操作の始めに黒板に書かれている数 x は 14 である.x を 3 で割った余り r は 2 であるため,黒板に書かれている数を,x=14 に 3 を掛けた数である 42 に書き換える.
4 回操作したとき初めて黒板に書かれている数が 40 以上になるため,4 を出力する.
入力例 2
3 4
出力例 2
1
入力例 3
20 62
出力例 3
3
入力例 4
1 100000
出力例 4
19