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

Фермеру Джону сообщили о местонахождении сбежавшей коровы, и он хочет немедленно ее поймать. Он начинает с точки n на числовой прямой, а корова находится в точке k на той же числовой прямой. У фермера Джона есть два способа передвижения: ходьба и телепортация.

· Ходьба: ФД может переместиться из любой точки x в точку x – 1 или x + 1 за одну минуту;

· Телепортация: ФД может переместиться из любой точки x в точку 2 * x за одну минуту.

Если корова, не подозревая о преследовании, вообще не двигается, сколько времени понадобится фермеру Джону, чтобы ее поймать?

Вход. Одна строка содержит два целых числа n (0 ≤ n ≤ 10⁵) и k (0 ≤ k ≤ 10⁵).

Выход. Выведите наименьшее количество минут, за которое фермер Джон поймает сбежавшую корову.

Пример входа	Пример выхода
5 17	4

РЕШЕНИЕ

поиск в ширину

Анализ алгоритма

Абсциссы на координатной прямой рассмотрим как вершины графа. Способы передвижения задают ребра на графе. Например, перемещение вправо задает ребро (x, x + 1) для некоторой координаты x, а телепортация – ребро (x, 2 * x).

Наименьшее количество минут, за которое фермер Джон поймает сбежавшую корову, равно кратчайшему пути между вершинами n и k. Для его нахождения запускаем поиск в ширину из вершины n и выводим кратчайшее расстояние до вершины k.

Пример

Самый быстрый способ для фермера Джона добраться до сбежавшей коровы – двигаться по следующему пути: 5 – 10 – 9 – 18 – 17, что занимает 4 минуты.

Рассмотрим пошаговое заполнение массива кратчайших расстояний dist.

Реализация алгоритма

Объявим массив кратчайших расстояний dist и очередь q для поиска в ширину.

#define MAX 200001

int dist[MAX];

queue<int> q;

Функция go реализует переход из вершины v в to. Если dist[to] ≠ -1, то вершина to уже посещалась ранее и мы не можем идти в to.

void go(int v, int to)

{

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

Заносим вершину to в очередь. Пересчитываем кратчайшее расстояние dist[to].

q.push(to);

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

}

Функция bfs реализует поиск в ширину из вершины start.

void bfs(int start)

{

Инициализация данных для поиска в ширину.

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

dist[start] = 0;

q.push(start);

Основной цикл – продолжаем его пока очередь не пуста.

while (!q.empty())

{

Достаем вершину x из головы очереди.

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

Если мы пришли в позицию k, где стоит корова, то завершаем поиск.

if (x == k) return;

Рассматриваем способы передвижения – вправо, влево и телепортацию. Если ход возможен, то пересчитываем массивы.

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

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

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

}

}

Основная часть программы. Читаем входные данные. Запускаем поиск в глубину из позиции n. Выводим ответ – наименьшее количество минут, за которое фермер Джон сможет попасть в позицию k.

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

bfs(n);

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