ЛШ 2005 (ст. группа) - 1

Problem G. Girl's game ≡

problems
visible spaces
basic formulae
wide text
editor

Author:	A. Klenin	Time limit:	1 sec
Input file:	input.txt	Memory limit:	64 Mb
Output file:	output.txt

Statement

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₁ = d_N = d_{d_i} = 0

There is always at least one sequence of dice throws allowing to finish the game.

Sample tests

No.	Input file (`input.txt`)	Output file (`output.txt`)
1	`2 0 0`	`1`
2	`3 0 0 0`	`1.166667`
3	`3 0 1 0`	`1.2`