第23回日本情報オリンピック　一次予選(第2回)

2023年10月16日
情報オリンピック日本委員会

問題文

正の整数 X, N が与えられる．

最初，黒板に整数 X が書かれている．

JOI 君は，以下の操作を繰り返し行う．

操作: 今，黒板に書かれている数を x とする．x を 3 で割った余りを計算し，r とする．r の値に応じて，黒板に書かれている数を以下のように書き換える．

• r=0 のとき，黒板に書かれている数を，x に 1 を足した数に書き換える．
• r=1 のとき，黒板に書かれている数を，x に 2 を掛けた数に書き換える．
• r=2 のとき，黒板に書かれている数を，x に 3 を掛けた数に書き換える．

黒板に書かれている数が N 以上になるまでに必要な操作の回数を求めよ．

制約

• 1 ≦ X ＜ N ≦ 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