Catch That Cow
| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 78114 | Accepted: 24667 |
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.
Source
#include "iostream"
#include "fstream"
#include "sstream"
#include "cstdio"
#include "queue" using namespace std ;
const int maxN = 1e5 + 1e3 ;
const int Max_Limit = 1e5 ;
const int INF = ;
typedef long long QAQ ; queue < int > Q ;
bool vis[ maxN ] ;
int step[ maxN ] ;
int K , N ; bool Check ( int x_x ) { return x_x == K ? true : false ; } int BFS ( ) {
int temp ;
bool Get_Target = false ;
Q.push ( N ) ;
vis[ N ] = true ;
while ( !Q.empty ( ) ) {
int tmp = Q.front ( ) ;
Q.pop ( ) ;
for ( int i= ; i< ; ++i ) {
switch ( i ) {
case :{
temp = tmp - ;
break;
}
case :{
temp = tmp + ;
break;
}
case :{
temp = tmp * ;
break;
}
} if ( temp > Max_Limit || temp < ) continue ;
if ( !vis[ temp ] ) {
Q.push( temp ) ;
step[ temp ] = step[ tmp ] + ;
vis[ temp ] = true ;
if ( Check ( temp ) ) {
Get_Target = true ;
return step[ temp ] ;
}
}
}
}
if ( !Get_Target ) return - ;
} int main ( ) {
scanf ( "%d %d" , &N , &K ) ;
if ( N >= K ) {
printf ( "%d\n" , N - K ) ;
goto End ;
}
printf ( "%d\n" , BFS ( ) ) ;
End :
return ;
}
2016-10-19 21:59:12