Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. 农夫约翰已经获悉逃跑的牛的位置,想立刻抓住它。
He starts at a point N (0 ≤ N ≤ 100,000) on a number line and the cow is at a point K (0 ≤ K ≤ 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting.
农夫约翰位于数轴上的点 N(0 ≤ N ≤ 100,000)处,奶牛位于同一数轴的点 K(0 ≤ K ≤ 100,000)处,他有两种移动方式:步行和闪移。
X to the points X - 1 or X + 1 in a single minute
步行:每分钟可以从点 X 移动到 X - 1 或 X + 1X to the point 2 * X in a single minute.
闪移:每分钟可以从点 X 移动到 2 * XIf the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it? 假设奶牛始终静止不动,请求出 Farmer John 抓住奶牛所需的最少时间(单位:分钟)。
第一行:两个空格分隔的整数 N 和 K
第一行:Farmer John 抓住奶牛所需的最少分钟数
5 17
4
最快路径为 5 → 10 → 9 → 18 → 17,共耗时4分钟。
注意移动时下标防止越界,允许往回走。