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
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