Catch That Cow

Time Limit:2000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u

Submit

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.

由于移动方式只有 +1 -1 *2 因此如果 起点大于终点，直接相减即可 剩下就是标准的BFS模板

1 /* 2 By:OhYee 3 Github:OhYee 4 Email:oyohyee@oyohyee.com 5 Blog:http://www.cnblogs.com/ohyee/ 6  7 かしこいかわいい？ 8 エリーチカ！ 9 要写出来Хорошо的代码哦~10 */11 12 #include 
        
         13 #include 
         
          14 #include 
          
           15 #include 
           
            16 #include 
            
             17 #include 
             
              18 #include 
              
               19 #include 
               
                20 #include 
                
                 21 #include 
                 
                  22 using namespace std;23 24 //DEBUG MODE25 #define debug 026 27 //循环28 #define REP(n) for(int o=0;o
                  
                    v)36 return s - v;37 38 queue
                   
                     Q;39 bool visited[maxn];40 memset(visited,false,sizeof(visited));41 int dis[maxn];42 memset(dis,0,sizeof(dis));43 44 Q.push(s);45 visited[s] = true;46 while(!Q.empty()) {47 int th = Q.front();48 Q.pop();49 50 //达到终点51 if(th == v)52 break;53 54 //拓展节点55 56 #define push \57 if(next > maxn || next <= 0) \58 continue;\59 if(!visited[next]) {\60 Q.push(next);\61 visited[next] = true;\62 dis[next] = dis[th] + 1;\63 }\64 65 66 int next;67 next = th + 1;68 push;69 next = th - 1;70 push;71 next = th * 2;72 push;73 }74 75 if(dis[v])76 return dis[v];77 else78 return -1;79 }80 81 bool Do() {82 int s,v;83 if(scanf("%d%d",&s,&v)==EOF)84 return false;85 printf("%d\n",BFS(s,v));86 return true;87 }88 89 int main() {90 while(Do());91 return 0;92 }