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