#P1306. 哆啦A梦的时光机
哆啦A梦的时光机
题目描述
哆啦A梦有一个神奇的道具:时光机。坐着它,大雄和他的伙伴们能穿越时空,回到过去或者去到未来。
有一天,大雄和他的伙伴们想穿越时空进行探险,可是时光机却出了一点故障,只能进行有限的时空穿越操作。大雄他们需要从现在出发,到达一个目标时间点进行探险,结束后再返回到现在。他们希望尽可能减少时光机的操作次数,你能帮助他们吗?
假设大雄和他的伙伴们出发的时间点(现在)为S,希望到达的时间点(目标)为T,已知时光机可以进行如下的时空穿越操作(X为正整数):
- 可以从任意时刻X穿越到X+1或者X-1时刻
- 可以从任意时刻X穿越到X×2时刻
- 当X为偶数时,可以从X时刻穿越到X/2时刻
请问,大雄和他的伙伴们从S时刻出发,先到达T时刻,再回到S时刻最少需要多少次时空穿越操作?
输入格式
两个正整数S和T(0<S, T≤1000000, S!=T),表示出发和到达时间点。
输出格式
一个正整数,表示最少时光机操作次数。
输入/输出样例
5 17
8
4 8
2
说明/提示
时间1000ms,内存256MiB