Задача B. Гейм-дизайн

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:256 Мб
Максимальный балл:8  

Условие

Компания по разработке настольных игр планирует к выпуску простую игру. Игра ведётся на полоске из N клеток, пронумерованных от 1 до N слева направо. Каждая клетка либо пуста, либо содержит число в диапазоне от 1 до N − 1.

На первом ходу фишка игрока находится на клетке номер 1. Во время ходя игрок кидает кубик, получая равномерно распределённое число в диапазоне от 1 до 6. Игрок двигает фишку вправо на выпавшее количество клеток. Если новая клетка пуста, то фишка остаётся на ней, а если клетка содержит число k, то фишка немедленно перемещается в клетку номер k.

Игра заканчивается, когда игроку выпало число, требующее переместить фишку на последнюю клетку или ещё правее.

Чтобы сбалансировать игру, требуется определить среднюю продолжительность игры, то есть математическое ожидание количества ходов до окончания игры.

Формат входных данных

Первая строка входных данных содержат целое число N.

Вторая строка содержит N целых чисел di, где di = 0 если ячейка пуста, либо содержит номер ячейки на которую следует перейти при попытке пойти в ячейку i.

Формат выходных данных

Выходные данные должны содержать единственное вещественное число с абсолютной ошибкой не более 10 − 3 — математическое ожидание количества ходов.

Ограничения

2 ≤ N ≤ 25, 0 ≤ di ≤ N − 1, d1 = dN = ddi = 0

Гарантируется, что существует хотя бы одна последовательность ходов, приводящая к окончанию игры.

Примеры тестов

Стандартный вход Стандартный выход
1
2
0 0
1
2
3
0 0 0
1.166667
3
3
0 1 0
1.2

0.103s 0.017s 13