TopCoder

Caido
Waimai

User's AC Ratio

93.6% (339/362)

Submission's AC Ratio

44.7% (465/1041)

Tags

Description

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

  • 乘以 21,即 K=2K+1
  • 乘以 2,即 K=2K
  • 除以 2,即 K=K/2

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

Input Format

包含兩個數字A,B (0A,B231)。

Output Format

請輸出最小操作次數 N

Sample Input 1

17
15

Sample Output 1

7

Hints

Problem Source

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

Subtasks

No. Testdata Range Score
1 0 20
2 1 20
3 2 20
4 3 20
5 4 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5