TopCoder

Thumb kagatioj
Pooh
我有智乃抱枕了喔喔喔喔喔喔喔

User's AC Ratio

98.1% (101/103)

Submission's AC Ratio

59.3% (128/216)

Description

對於字串來說,Edit Distance是一個著名的DP問題。現在我們把這個問題弄得簡單一點,例如:把字串換成數字。對於一個數字$A$,我們想要藉由某些操作換成數字$B$。而對於整數$K$的一個合法的操作包括以下三種情形:

  • 乘以 $2$ 加 $1$,即 $K=2K+1$
  • 乘以 $2$,即 $K=2K$
  • 除以 $2$,即 $K=\lfloor K/2\rfloor$

給定整數 $A$ 和 $B$,請你求出最小的操作次數 $N$使得從 $A$ 開始操作 $N$ 次可以換成 $B$。

Input Format

包含兩個數字$A, B$ ($0 \leq A, B \leq 2^{31}$)。

Output Format

請輸出最小操作次數 $N$。

Sample Input

17
15

Sample Output

7

Hints

Problem Source

原TIOJ1011 / 95建中資訊培訓模擬試題一(Prob 3)

Subtasks

For Testdata: 0 ~ 0, Score: 20
For Testdata: 1 ~ 1, Score: 20
For Testdata: 2 ~ 2, Score: 20
For Testdata: 3 ~ 3, Score: 20
For Testdata: 4 ~ 4, Score: 20
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 1000 65536 65536