Ежедневная часть (e) C++ # 44, Общая проблема интервью C++: качающееся движение
Сегодня мы рассмотрим распространенный вопрос на собеседовании по C++: раскачивающееся движение.
Учитывая начальную позицию и пункт назначения (положительные целые координаты), определите, можно ли достичь пункта назначения с помощью качающегося движения. То есть мы можем перейти из позиции {x,y} либо в {x+y,y}, либо в {x,x+y}.
Прежде чем продолжить чтение решения, я рекомендую вам попробовать решить его самостоятельно. Вот ссылка на Compiler Explorer с парой тестов: https://compiler-explorer.com/z/TTshG4Ph3.
Решение
Основное наблюдение для этой проблемы состоит в том, что операция «качания» полностью обратима. Координата назначения {x,y} может быть достигнута только из {x-y,y} или {x,y-x}. Кроме того, поскольку наши координаты — положительные целые числа, возможно только одно из двух направлений.
Из-за этой обратимости для любого пункта назначения существует только один возможный обратный путь, ведущий от (к) этому пункту назначения. Поэтому мы можем проследить этот путь, проверяя, достигаем ли мы в какой-либо точке нашей исходной координаты.
Этот подход, однако, имеет неприятную проблему, связанную с линейностью (рассмотрите случай {1,1}→{MAX_INT, 1}).
К счастью, есть операция по модулю, которую мы можем использовать вместо многократного применения минусовой операции.
Однако нам нужно быть осторожными. Рассмотрим случай: {7,15}→{7,29}. Если мы прямо применим операцию по модулю, мы можем пропустить наш пункт назначения, перейдя от {7,29} прямо к {7,1}. Примечательно, что это происходит только тогда, когда одна из координат уже верна.
struct Coord {
unsigned x;
unsigned y;
friend auto operator <=>(const Coord&, const Coord&) = default;
};
bool is_reachable(Coord src, Coord dst) {
// We overshot, meaning that the destination is not reachable.
if (src.x > dst.x || src.y > dst.y)
return false;
// We hit the source, the destination is reachable.
if (src == dst)
return true;
if (dst.x > dst.y) {
if (src.y != dst.y)
// recurse
return is_reachable(src, {dst.x % dst.y, dst.y});
else
// make sure we don't skip over src.x
return (dst.x % dst.y) == (src.x % dst.y);
} else {
if (src.x != dst.x)
// recurse
return is_reachable(src, {dst.x, dst.y % dst.x});
else
// make sure we don't skip over src.y
return (dst.y % dst.x) == (src.y % dst.x);
}
}
