Задача 575
Блуждающие роботы

В один достаточно обыкновенный день загадочный инопланетный корабль появился словно из ниоткуда. Прождав несколько часов и не получив никакого ответа, было решено отправить команду исследователей, в которую включили вас. Внутри корабля вас встретила дружелюбная голографическая голограмма Катарина, которая объяснила вам суть корабля Эйлертопии.

Она утверждает, что Эйлертопия стара, как само время. Миссия корабля - использовать комбинацию неимоверной вычислительной мощи и длительных промежутков времени, что найти ответ на главный вопрос жизни, вселенной и всего такого. Потому местный робот-уборщик Леонард, в дополнение к обязанностям уборки, был создан с мощной вычислительной матрицей для поиска смысла жизни, пока он бродит по огромной сети комнат 1000 на 1000. Катарина объясняет, что комнаты пронумерованы по порядку слева направо, ряд за рядом. Так, например, если бы Леонард бродил по сетке 5 на 5, комнаты были бы пронумерованы следующим образом:

p575_wandering_robot_1_5x5.png

Много тысячелетий назад Леонард сообщил Катарине, что он нашел ответ и готов поделиться им с любой формой жизни, которой покажет себя достойной такого знания.

Далее Катарина объяснила, что создателям Леонарда было сказано запрограммировать его с равной вероятностью остаться в той же комнате или переместиться в смежную комнату. Однако, им не было понятно, значило ли это (i) равную вероятность, разделенную одинаково между "остаться в комнате" и количеством возможных путей, или же (ii) равную вероятность (50%) остаться в той же комнате, и остальные 50%, разделенные одинаково между всеми возможными путями.

p575_wandering_robot_2_fixed.pngp575_wandering_robot_3_dynamic.png
(i) Вероятность остаться зависит от количества выходов(ii) Фиксированная вероятность остаться 50%

Записи показывают, что они решили бросить монету. Решка значит, что вероятность остаться будет динамически зависеть от количества выходов, в то время как орел значит, что они запрограммируют Леонарда с фиксированной вероятностью 50% остаться в конкретной комнате. К сожалению, запись резудьтата броска монеты не сохранилась, поэтому нам придется предположить, что существует одинаковая вероятность внедрения одного или другого алгоритма действий.

Катарина предполагает, что не слишком сложно определить, что вероятность найти Леонарда в комнате с номером, являющимся квадратом целого числа, в сетке 5 на 5 после неизмеримо долгого времени будет примерно равна 0.177976190476 (12 знаков после десятичной точки).

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

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