Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду Сместиться на (a,b) (где a, b — целые числа), перемещающую Чертёжника из точки с координатами (x, y) в точку с координатами (x +a, y +b). Если числа a, b положительные, значение соответствующей координаты увеличивается, если отрицательные — уменьшается. Например, если Чертёжник находится в точке с координатами (2, 3), то команда Сместиться на (-5,2) переместит Чертёжника в точку (-3, 5).
Чертёжнику был дан для исполнения следующий алгоритм (количество повторений и величины смещения в первой из повторяемых команд неизвестны):
НАЧАЛО
Сместиться на (-1, -2)
ПОВТОРИ … РАЗ
Сместиться на (… , …)
Сместиться на (-1, -2)
КОНЕЦ ПОВТОРИ
Сместиться на (-20, -12)
КОНЕЦ
В результате выполнения этого алгоритма Чертёжник возвращается в исходную точку. Какое наибольшее число повторений могло быть указано в конструкции «ПОВТОРИ … РАЗ?
Решение руками
Запишем условие в виде системы:
 |
 |
Можно заметить, что нам требуется такое максимальное число k, чтобы оно было делителем и 21, и 14, т.е. НОД этих чисел. НОД(21,14)=7.
Решение программой
for n in range(100):
for a in range(-500, 500):
for b in range(-500, 500):
x = y = 0
x = x - 1
y = y - 2
for i in range(n):
x = x + a
y = y + b
x = x - 1
y = y - 2
x = x - 20
y = y - 12
if x == 0 and y == 0:
print(n)
break