Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

Блог пользователя Diamond-_-

Автор Diamond-_-, 3 года назад, По-русски

Попробуем разобрать задачу H из высшей лиги Декабрьского кубка. Надеюсь, это поможет вам при решении схожих задач. Приступим к разбору: Разумеется, если при вводе x=0 и y=0, то сразу выведем 0. Дальше заведем 3 переменные: newPosX = 0, newPosY = 0, vectorMove = 2; newPosX, newPosY — Мы 4 раза запустим программу для робота, и после этих действий, это то, насколько изменилась позиция во время "цикла". (цикл — 4 программы робота подряд, после выполнения цикла направление робота останется таким же) vectorMove — направление движения.

Дальше во вложенном цикле реализуем движение робота (учитывая то, что vectorMove может стать равным 0 или 5).

for (int i = 0; i < 4; i++)
{
for (int j = 0; j < n; j++)
{
if (s[j] == 'F' && vectorMove == 2)
newPosX += 1;
if (s[j] == 'F' && vectorMove == 4)
newPosX -= 1;
if (s[j] == 'F' && vectorMove == 1)
newPosY += 1;
if (s[j] == 'F' && vectorMove == 3)
newPosY -= 1;

    if (s[j] == 'L')
       vectorMove -= 1;
    if (s[j] == 'R')
       vectorMove += 1;
    if (vectorMove == 5)
       vectorMove = 1;
    if (vectorMove == 0)
       vectorMove = 4;
    if (newPosX == x && newPosY == y)
    {
       cout << i * n + j + 1;
       return 0;
    }
}

}

if (newPosX == 0 && newPosY == 0)
{
cout << -1;
}
int q1=0, q2=0; // предполагаемое к-во циклов по X/Y
if (мы движемся по X не в том направлении)
{
q1=0;
}
else
{
if (newPosX == 0)
q1 = y / newPosY; /* нам по сути без разницы чему
в этом случае равно q1, но в дальнейшем
мы будем писать ... min(q1,q2) ... /
else
q1 = x / newPosX;
}
if (мы движемся по Y не в том направлении)
{
q2=0;
}
else
{
if (newPosY == 0)
q2 = x / newPosX; /
В отношении этого случая комментарий
находится выше */
else
q2 = y / newPosY;
} q1 = max((int64_t)0, q1 — 4 * n — 1); // Это делается для того чтобы не получилось так, что во время одного из циклов робот доехал до точки назначения раньше чем пройдет q1 циклов и у нас был бы "Неправильный ответ на тесте N"
q2 = max((int64_t)0, q2 — 4 * n — 1); // см. комментарий выше

Заведем переменную ans, которая будет промежуточным результатом.
Далее удостоверившись, что "начальная" позиция(после выполнения некоторого к-ва циклов) не совпадает с конечной, выполняем программу робота.
Если мы дошли до конечной точки, то выведем ответ.
Иначе выведем -1.
Всем удачи!
Code

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится