Catch That Cow

Description

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.

* Walking: FJ can move from any point X to the points X - 1 or X + 1 in a single minute
* Teleporting: FJ can move from any point X to the point 2 × X in a single minute.

If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?

Input

Line 1: Two space-separated integers: N and K

Output

Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.

Sample Input

5 17

Sample Output

4

Hint

The fastest way for Farmer John to reach the fugitive cow is to move along the following path: 5-10-9-18-17, which takes 4 minutes.

View Code

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<string.h>
 4 #include<math.h>
 5 const int M = 1000005;
 6 int n, m, q[2*M], front, last, h[2*M];
 7 int judge( int x )
 8 {
 9     if( x < 0 || x >= 2*M || h[x] )
10          return 0;
11     return 1;
12 }
13 
14 int BFS( int a, int b )
15 {
16     front = last = 0;
17     q[front++] = a;
18     if( a == b )
19          return 0;
20     while( last < front )
21     {
22            
23            int x = q[last++];
24            if( x+1 == b || x-1 == b|| 2*x == b )
25                  return h[x]+1;
26            if( judge( x+1) )
27            {
28                h[x+1] = h[x]+1,q[front++] = x+1;
29            }
30            if( judge(x-1) )
31            {
32                h[x-1] = h[x]+1,q[front++] = x-1;
33            }
34            if( judge(2*x) )
35            {
36                h[2*x] = h[x]+1,q[front++] = 2*x;
37            } 
38     }
39     return -1; 
40 }
41 
42 int main()
43 {
44     while( scanf( "%d%d", &n, &m) == 2 )
45     {
46            for( int i = 0; i < 2*M; i++ )
47                   h[i] = 0;
48            printf( "%d\n", BFS( n, m ) );
49     }
50     return 0;
51 }