3728 - X之于Y
Description

Noder 上课无聊摸鱼,他在纸上随意写下了两个数字 X 和 Y。现在他想把 X 通过某种方法变成 Y,为了把这个过程更加有趣,所以他限定自己只能使用两种操作:
1. 把当前 X 乘二(X = X * 2)
2. 把当前 X 减一(X = X - 1)
因为课堂上的时间有限,所以他用了最少的操作次数实现这一过程。下课后,路过的 qz 看到了 Noder 纸上写着的 X 和 Y,他一秒钟以内就知道了 Noder 用了多少次操作。那么问题来了,Noder 到底用了多少次操作呢?

Input

两个数字表示 X 和 Y。其中:
1 <= X <= 1,000,000,000
1 <= Y <= 1,000,000,000

Output

一个数字,表示把 X 变成 Y 最少需要多少次操作。

Examples

Input

1 1000000000

Output

39
Hint

当 X >= Y 时只能一路减一,答案为 X - Y。当 X < Y 时从 Y 逆向考虑:逆向操作为“若当前为偶数则除以 2”“当前加 1”(分别对应正向的 ×2 与 −1)。贪心地不断把 Y 往小的方向压:Y 为偶数就 Y/=2,Y 为奇数就 Y+=1,直到 Y <= X,剩下的差用减一补齐(X - Y 步)。这样得到的就是最少操作数。

Source
51nod 2595
Tags
题目参数
Time Limit 1 second
Memory Limit 128 MB
提交次数 1
通过次数 1