Задача #1963
Исполнитель Черепаха
(Е.Джобс) Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии.
После выполнения команды «Поднять перо» чертежник перестает оставлять след и перемещается согласно приведенному алгоритму. После выполнения команды «Опустить перо» чертежник начинает оставлять след. В начальный момент перо опущено, то есть чертежник при перемещении будет оставлять след.
Чертёжник может выполнять команду Сместиться на (a,b) (где a, b — целые числа), перемещающую Чертёжника из точки с координатами (x, y) в точку с координатами (x+a, y+b). Если числа a, b положительные, то значение соответствующей координаты увеличивается, если отрицательные — уменьшается. При выполнении команды Сместиться в (x, y) чертежник перемещается в точку с координатами (х, у).
Запись Повтори k [Команда1 Команда2 … КомандаS] означает, что последовательность из S команд повторится k раз.
Чертёжнику был дан для исполнения алгоритм:
Определите количество точек с целочисленными координатами, лежащих на оставленном чертежником следе.
Решение
Ответ
При изменении масштаба заметим, что точки пересечения не находятся в точках с целочисленными координатами.
Целочисленные точки:
1 - начало следа
12 - первая линия - НОД(60, 156)
1 - вторая линия - НОД(140, 153)
далее смещение на (-129, 77) - еще 1 точка - НОД(129, 77)
1 - первая линия "циклического" следа - НОД(111, 77)
12 - втораялиния "циклического" следа - НОД(60, 156)
1 - третья линия "циклического" следа - НОД(140, 153)
далее перемещение из точки (71-111+60+140, 80+77+156-153) = (160, 160) в точку (71, 80). Или смещение на (-89, 80). НОД(89, 80) = 1 (начальная точка циклического следа)
Итого: 1+12+1+1+1+12+1 = 29