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 и 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 уже была посещена ранее, и повторно в неё заходить не нужно.

void go(int v, int to)

{

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

Если вершина to ещё не посещалась, добавляем её в очередь q и обновляем значение dist[to], прибавив единицу к расстоянию от вершины v.

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]);