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:

 ``````1 `````` ``````5 17 ``````

output:

 ``````1 `````` ``````4 ``````

## Solution

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 `````` ``````#include #include #include using namespace std; // x may >K, for example, // K=100000,N=50001, then // (x*2)->(x-1)->(x-1) // may be the best choice, // so MAXLEN must be large enough const int MAXLEN=200002; int N,K; bool location[MAXLEN]; struct node{ int x,step; }; queue q; void BFS(){ int x,step; int x1,x2,x3; while(!q.empty()){ node n1=q.front(); q.pop(); x=n1.x; step=n1.step; // 3 choices of actions x1=x-1, x2=x+1, x3=x*2; if(x==K){ printf("%d\n",step); return; } // 3 branches correspond to 3 branches in decision tree if(x>0 && location[x1]==0){ location[x1]=1; node n2={x1,step+1}; q.push(n2); } if(x