Робот-черепашка сначала смотрит на север. За один шаг может двинуться на N (N >= 1) клеток туда, куда смотрит, после чего сразу поворачивается на 90 грд. по часовой стрелке.

Входная программа — ряд целых чисел любой длины. Например: 1,7,3,4,5,1. (1 на север, 7 на восток, 3 на юг, 4 на запад, 5 на север, 1 на восток). Каждый шаг — не менее 1.

Написать код, который бы возвращал ближайший номер шага (от начала программы), на котором черепашка проедется по собственному пути. То есть, по клетке, на которой она уже была. Стоимость алгоритма по процу — не более O(N), стоимость алгоритма по памяти — постоянная ( O(1) ).

Нарисовал картинку, из которой видно одно свойство алгоритма — если черепашка когда-либо наезжает на собственный путь на неком шаге M, то этот наезд всегда происходит на ту линию, которая была построена на шаге M-3, либо M-5. Всё.

1. Это наколеночное решение, выведенное умозрительно, без доказательств.
2. История про робота-черепашку — боян 40-летней давности (или больше), над которым бились все великие бородатые изобретатели алгоритмов, поэтому любое своё решение просто психологически идёт в корзину.

Свойства шагательного алгоритма таковы, что черепашка либо поедет по постоянно раскручивающейся спирали (конечной, если конечно значение целого числа в программе), либо (сделав хоть один ход, не выносящий её за "очертания" спирали, обязательно на себя наедет, максимум продлив себе "жизнь" закручиванием спирали.

Картинка, из которой видны свойства шагательного алгоритма (красным показаны линии, на которые совершается наезд). Зелёная точка — возможные альтернативы развития событий для рассмотрения разных вариантов.

Картинка: http://files.rsdn.ru/99419/Note_20130224_230725_06-2.jpg ( 144 KB )

Обсудите (-;