ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Open Ural SU Championship 2010

About     Problems     Submit solution     Judge status     Standings
Contest is over

C. Anniversary Firework

Time limit: 1.0 second
Memory limit: 64 MB
Denis has to prepare the Ural State University 90th anniversary firework. He bought n rockets and started to think of the way he should launch them. After a pair of sleepless nights he invented the following algorithm.
All n rockets are placed on the surface in a single line. The interval between two consecutive salvos is ten seconds. The leftmost and the rightmost rocket are launched in the first salvo. After i salvos are fired, all non-empty segments between two neighboring launched rockets are considered. One rocket is chosen randomly and uniformly at each of these segments. All chosen rockets are launched in the (i + 1)-st salvo. Algorithm runs until all rockets are launched.
Calculate the average duration in seconds of such a firework.


The only input line contains an integer n (3 ≤ n ≤ 400), which is the number of rockets bought by Denis.


Output the expected duration of the firework in seconds, with absolute or relative error not exceeding 10−6.




First, the rockets with numbers 1 and 5 are launched. 10 seconds later the rocket 3 is launched with probability 1/3; in that case, 10 more seconds later the rockets 2 and 4 are launched, and the firework is over after 20 seconds. In case the rocket 2 or rocket 4 is launched in the second salvo (this happens with probability 2/3), the firework is over after 30 seconds.
Problem Author: Alex Samsonov
Problem Source: XV Open USU Championship
To submit the solution for this problem go to the Problem set: 1776. Anniversary Firework