print1486. Girl's game

printGirl's game

Ограничения: время – 100ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Young programmer Vasya has a little sister. She likes to play tabletop games, and constantly nags her brother to play with her.
One game she particularly enjoys is played with a dice and a long board. The board is divided into a sequence of N cells. A player starts from the first cell. Each turn, the player throws the dice, obtaining an evenly distributed random number from 1 to 6. The player advances forward by the number of cells equal to the number on the dice. Destination cell is either empty, or contains instruction "jump to the `K`-th cell". In the latter case, the player immediately moves to the `K`-th cell instead of the destination cell.
The game ends when the number on the dice is equal to or greater than the number of cells left to the end of the board.
Vasya finds the game rather boring, especially the fact that the instructions on the cells keep sending you back again and again, dragging the game indefinitely.
Vasya wants to calculate the expected value (also known as the mathematical expectation) of the number of moves, so he could estimate the average time required to finish the game.
Input file format
Input file contains an integer `N`, followed by `N` integers `d_i`, where `d_i` = 0 if the cell is empty or contains the number of cell (from `1` to `N\ -\ 1`) where the player must move instead of the `i`-th cell.
Output file format
Output file must contain a single floating point number – expected value of the number of turns with the absolute error of at most `10^{-3}`.
Constraints
`2\ ≤\ N\ ≤\ 25`, `d_1\ =\ d_N\ =\ d_{d_i}\ =\ 0`
There is always at least one sequence of dice throws allowing to finish the game.

Sample Input 1

2 0 0

Sample Output 1

1

Sample Input 2

3 0 0 0

Sample Output 2

1.1667

Sample Input 3

3 0 1 0

Sample Output 3

1.2
Source: NEERC ICPC, Far Eastern subregion, 2008

loading