7748. Поймай эту корову

Farmer John has received information about the location of a runaway cow, and he immediately sets off to catch her. He starts at point n on the number line, while the cow is located at point k on the same line. Farmer John has two modes of transportation:

· Walking: FJ can move from any point x to x − 1 or x + 1 in one minute;

· Teleportation: FJ can move from any point x to 2 * x in one minute.

Since the cow is unaware of being pursued, she does not move. Determine the minimum amount of time it will take Farmer John to catch her.

Input. A single line contains two integers n (0 ≤ n ≤ 10⁵) and k (0 ≤ k ≤ 10⁵) – the starting positions of Farmer John and the cow, respectively.

Output. Print the minimum number of minutes required for Farmer John to reach the cow.

Sample input	Sample output
5 17	4

SOLUTION

breadth first search

Algorithm analysis

We can consider the positions on the number line as vertices of a graph, and the possible movements as edges of this graph. For example, a step to the right represents an edge between vertices x and x + 1, while teleportation represents an edge between x and 2 * x.

The minimum number of minutes it takes for Farmer John to catch the escaped cow corresponds to the length of the shortest path between vertices n and k. To find this path, we use a breadth-first search starting from vertex n. The answer is the shortest distance to vertex k.

Example

Let’s look at the fastest route Farmer John can take to reach the cow: 5 → 10 → 9 → 18 → 17. This takes 4 minutes.

Let’s now examine the step-by-step filling of the shortest distance array dist.

Algorithm implementation

Declare the array dist to store the shortest distances and a queue q to perform the breadth-first search.

#define MAX 200001

int dist[MAX];

queue<int> q;

The go function handles the transition from vertex v to vertex to. If dist[to] ≠ -1, it means that the vertex to has already been visited, and there is no need to visit it again.

void go(int v, int to)

{

if (dist[to] != -1) return;

If the vertex to is not visited yet, add it to the queue q and update the value of dist[to] by adding one to the distance from vertex v.

q.push(to);

dist[to] = dist[v] + 1;

}

The function bfs implements a breadth-first search starting from the vertex start.

void bfs(int start)

{

Initialize the data necessary for the breadth-first search.

memset(dist, -1, sizeof(dist));

dist[start] = 0;

q.push(start);

Start the main loop, which continues until the queue becomes empty.

while (!q.empty())

{

Extract vertex x from the front of the queue.

int x = q.front(); q.pop();

If the position k, where the cow is located, is reached, terminate the search.

if (x == k) return;

Consider all possible moves – to the right, to the left, and teleportation. If a move is possible, update the corresponding arrays.

if (x + 1 < MAX) go(x, x + 1);

if (x - 1 >= 0) go(x, x - 1);

if (2 * x < MAX) go(x, 2 * x);

}

}

The main part of the program. Read the input data. Run a breadth-first search starting from position n. Print the answer – the minimum number of minutes it takes for Farmer John to reach position k.

scanf("%d %d", &n, &k);

bfs(n);

printf("%d\n", dist[k]);