| Входной файл: | Стандартный вход | Ограничение времени: | 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 | |
|
| 3 | |
|