E. Хиякугоку и лестницы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Хиякугоку недавно покинула должность местного божежства Южного Храма Черной Улитки в погоне за своей мечтой стать художником мультфильмов. Шесть месяцев она только и делала, что играла в веревочку («Cat's Cradle»), и теперь решила попробовать новую игру — «Змеи и лестницы» («Лила»). К сожалению, все змеи оказались истреблены, поэтому остались лишь только лестницы.

Игра происходит на доске $$$10 \times 10$$$ по следующим правилам:

  • В начале игры игрок стоит в левой нижней клетке.
  • Цель игры заключается в достижении игроком финиша (левой верхней клетки). Как только он достигает финиша, игра заканчивается.
  • Путь выглядит следующим образом: если клетка находится не на краю ряда, то она ведет в следующую клетку по направлению движения ряда; если на краю, то ведет в ячейку выше. Направление движение ряда определяется так: направление в самом нижнем ряду — направо; направление в любом другом ряду противоположно направлению предыдущего ряда. В примечании есть изображение данного маршрута.
  • На каждом ходу игрок бросает стандартный шестигранный кубик. Пусть выпало некоторое число $$$r$$$. Если до финиша меньше $$$r$$$ ходов, тогда игрок остается на месте (но ход считается сделанным). Иначе игрок делает ровно $$$r$$$ шагов по своему пути и останавливается. Если игрок остановился в клетке, в которой находится основание лестницы, то игрок может выбрать, залезть по лестнице или нет. Если он выбирает не залезать, то к следующему ходу он остается в этой клетке.
  • В некоторых клетках есть лестницы. Лестницы расположены только вертикально — каждая ведет в ту же клетку в одном из рядов сверху.Игрок обязан остановиться в клетке, содержащей основание лестницы, после броска кубика, чтобы иметь возможность забраться по данной лестнице. После использования лестницы игрок оказывается в клетке, содержащей верхний конец лестницы. Нельзя слезть с лестницы в ходе восхождения. И если клетка, содержащая верхний конец лестницы, содержит также и основание другой лестницы, то вторую лестницу использовать нельзя.
  • Числа, написанные на кубике: 1, 2, 3, 4, 5 и 6 — у каждого одинаковая вероятность выпасть.

Обратите внимание, что:

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

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

Входные данные

Входные данные состоят из десяти строк. В $$$i$$$-й строке записаны 10 неотрицательных целых чисел $$$h_{i1}, h_{i2}, \dots, h_{i10}$$$. Если $$$h_{ij}$$$ равно $$$0$$$, то ячейка в $$$i$$$-й строке в $$$j$$$-м столбце не содержит лестницу. Иначе высота лестницы в данной клетке равна $$$h_{ij}$$$, то есть ее использование приведет в клетку, которая на $$$h_{ij}$$$ рядов сверху данной. Гарантируется, что $$$0 \leq h_{ij} < i$$$. Также первое число первой строки и первое число поледней строки всегда равны $$$0$$$, то есть стартовая и финишная клетки никогда не содержат лестниц.

Выходные данные

Выведите единственное вещественное число — минимальное математическое ожидание количества ходов, которые может занять игра. Ваш ответ будет засчитан, если его абсолютная или относительная ошибка не будет превосходить $$$10^{-6}$$$.

Примеры
Входные данные
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
Выходные данные
33.0476190476
Входные данные
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 3 0 0 0 4 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 4 0 0 0
0 0 3 0 0 0 0 0 0 0
0 0 4 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 9
Выходные данные
20.2591405923
Входные данные
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 6 6 6 6 6 6 0 0 0
1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
Выходные данные
15.9047592939
Примечание

Визуализация пути и поле для второго примера:

Клетка с 'S' — это стартовая клетка, клетка с 'E' — финиш.

В первом примере лестниц нет.

Во втором примере поле выглядит, как на втором изображении (лестницы раскрашена для наглядности).

Возможно, что лестницы накладываются, как в случае с красной и желтой, а также с зеленой и синей лестницами. Так же возможно, что лестницы ведут на самый верхний ряд, как черная и синия лестницы. Однако выше лестницы вести не могут (вне границ поля). Еще возможно, что две лестницы ведут в одну и ту же ячейку, как в случае с красной и желтой лестницами. Еще обратите внимание, что красная и желтая лестницы ведут в клетку с основанием оранжевой лестницы. Тогда если игрок выберет забираться по красной или желтой лестнице, то по оранжевой будет нельзя забираться. Наконец, обратите внимание, что зеленая лестница проходит через основние синей лестницы. Игрок не может слезть с зеленой и перебраться на синию, пока он использует зеленую лестницу.