Проблема :
Вы ставите цирковое представление с участием различных животных. На одно действие вам даются два кенгуру на числовой прямой, готовые прыгнуть в положительном направлении (т. е. в сторону положительной бесконечности).
* Первый кенгуру стартует в точке x1
и перемещается со скоростью v1
метра за прыжок.
* Второй кенгуру стартует в точке x2
и перемещается со скоростью v2
метра за прыжок.
Вы должны найти способ собрать обоих кенгуру в одном и том же месте в одно и то же время в рамках шоу. Если возможно, вернуть YES
, иначе вернуть NO
.
Например, кенгуру 1 начинает с x1 = 2
с дистанцией прыжка v1 = 1
, а кенгуру 2 начинает с x2 = 1
с дистанцией прыжка v2 = 2
. После одного прыжка они оба в x = 3
, ( x1 + v1 = 2 + 1
, x2 + v2 = 1 + 2
), поэтому наш ответ YES
.
Читать полностью задачу здесь — Кенгуру
Решение :
Здесь pos1
— текущая позиция кенгуру 1, а pos2
— текущая позиция кенгуру2. speed1
— это скорость кенгуру 1, а speed2
— скорость кенгуру 2. difference
хранит начальную разницу между их начальными позициями. Кенгуру, занявший последнее место, должен преодолеть это расстояние за difference
шагов, потому что минимальная скорость кенгуру равна 1
.
std::string no = "NO";
std::string yes = "YES";
int difference = abs(pos1 - pos2);
Следующая позиция для кенгуру — pos1 = pos1 + speed1
и pos2 = pos2 + speed2
. Если pos1
равно pos2
, значит, они встречались, и ответ YES
.
Случай 1: когда начальные позиции обоих кенгуру разные, т. е. pos1 != pos2
и difference != 0
.
Затем цикл будет выполняться difference
раз, и на каждом этапе их текущие позиции обновляются, и если их обновленные текущие позиции равны, возвращается YES
.
for (int i = 0; i < difference; ++i)
{
pos1 = pos1 + speed1;
pos2 = pos2 + speed2;
if (pos1 == pos2)
{
return yes;
}
}
if (pos1 != pos2)
{
return no;
}
Случай 2: когда начальные позиции обоих кенгуру одинаковы, т. е. pos1 == pos2
и difference == 0
.
Затем вычисляется следующее положение pos1 = pos1 + speed1
и pos2 = pos2 + speed2
, и если их скорости различны, то вычисляется новое difference
и выполняется как случай 1. Если их скорости одинаковы, то они встретятся на втором шаге.
if (difference == 0 && speed1 != speed2)
{
pos1 = pos1 + speed1;
pos2 = pos2 + speed2;
difference = abs(pos1 - pos2);
}
else if (difference == 0 && speed1 == speed2)
{
return yes;
}
Кенгуру никогда не встретятся, если кенгуру, который идет впереди, имеет большую скорость, чем последний кенгуру.
if ((pos1 > pos2 && speed1 > speed2) || (pos2 > pos1 && speed2 > speed1))
{
return no;
}
По теме: Вызов Roy and Code Streak HackerEarth Challenge
Для реализации C++ посетите Programmercave
Первоначально опубликовано на https://programmercave0.github.io 28 ноября 2019 г.