Задача 611
Квадратные шаги по коридору

Петр перемещается по коридору с N+1 дверями, последовательно пронумерованными от 0 до N. Изначально все двери закрыты. Петр начинает перед дверью 0 и повторяет следующие шаги:

  • Сначала он отходит от своей позиции на число дверей, равное квадрату целого числа.
  • Затем он отходит от своей новой позиции на число дверей, равное еще большему квадрату целого числа.
  • Он изменяет состоние двери, оказавшейся перед ним (открывает, если он закрыта, или закрывает, если открыта).
  • Наконец, он возвращается к двери 0.

Назовем любую последовательность этих шагов действием. Петр никогда не выполняет одно и то же действие дважды и выполняет все возможные действия, которые не приведут его дальше, чем последняя дверь.

Пусть F(N) будет количеством дверей, которые остались открытыми после того, как Петр выполнил все возможные действия. Известно, что F(5) = 1, F(100) = 27, F(1000) = 233 и F(106) = 112168.

Найдите F(1012).

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net