Задание №168132: Задание 3

Задача 3. Путь зигзагом

Будем увеличивать координаты чередуя их, пока не придём в нужную точку (x = a, y = b).
Если же одна координата уже приняла необходимое значение, а её нужно изменить, уменьшим её
на 1, потом она снова увеличится на 1, то есть эта координата будет меняться вблизи нужного нам
значения: a, a (cid:0) 1, a, a (cid:0) 1 и т.д., пока вторая координата не достигнет конечного значения.
В этом случае, возможно, мы сделаем лишний ход. Чтобы избежать этого лишнего хода, пер-
вое движение нужно делать в том направлении, в котором нам нужно переместиться на большее
расстояние, то есть если a > b, то на первом шаге нужно менять x, а если b > a — то y. Тогда мы
получим наилучший ответ.
Докажем это. Пусть m = max(a;b). Тогда мы должны сделать как минимум m шагов в одном
направлении, и ответ не может быть меньше m + (m (cid:0) 1), т.к. в другом направлении мы должны
сделать как минимум m (cid:0) 1 шагов. Более того, если a и b — одной чётности, то количества выпол-
ненных шагов в каждом направлении также должны быть одной чётности, и общее число шагов
будет не менее 2m. То есть общее число шагов не меньше 2m, если a и b одной чётности, и 2m (cid:0) 1,
если разной чётности.
Пусть a > b. Тогда выполнив a шагов по координате x мы окажемся либо в точке (a;b), либо в
точке (a;b(cid:0)1), так как по координате y робот будет «бегать» между y = b и y = b(cid:0)1. Поскольку мы
начали движение с координаты x, по оси y мы сделали на одно перемещение меньше, и координаты
робота будут разной чётности. В какой именно точке он окажется, зависит именно от чётности b,
поэтому в случае разных чётностей a и b он окажется в точке (a;b), и алгоритм завершит работу.

Если же a и b одной чётности, то робот окажется в точке (a;b (cid:0) 1), и ему понадобится сделать ещё
один шаг. Случай a < b рассматривается аналогично, в случае a = b наше решение достигнет цели
ровно за a + b шагов.
Пример решения. В этом решении в переменной move_x хранится логическое значение (True или
False), означающее, что робот делает очередной шаг вдоль оси OX. Это значение будет меняться
на противоположное на каждом шаге цикла.
a = int (input ())
b = int (input ())
move_x = a > b
x = 0
y = 0

while x != a or y != b:
if move_x:
if x < a :
x += 1
else :
x −= 1
else :
if y < b:
y += 1
else :
y −= 1

Страница 2 из 5

Пригласительный этап всероcсийской олимпиады по информатике для 8–10 классов
29-30 мая 2025

print (x , y)
move_x = not move_x