Quite recently, the City of Barcelona has included trams to its “efficient” public transport. As expected, the result has been a nice set of accidents of outstanding originality and beauty. But diminishing aesthetic reasons, the Mayor of Barcelona has decided to reduce the delay caused by the accidents. After a thorough study the following model has been established.

Every tram must go from an initial point *P*_{0} to a final point *P*_{n}
visiting the intermediate points *P*_{1}, …, *P*_{n−1} in this order.
For every 1 ≤ *i* ≤ *n*,
let *S*_{i} be the section that goes from *P*_{i−1} to *P*_{i}.
Every such section must be travelled at uniform speed *v*_{i},
which is chosen by the driver at *P*_{i−1}.
Let *M*_{i} be the maximum possible speed of the tram at *S*_{i},
and assume that the chosen speed is 0 < *v*_{i} ≤ *M*_{i}.
Then the probability of crashing in *S*_{i} is *v*_{i}/*M*_{i}.
When a crash happens,
the tram uses an efficient recovery system that lasts only 10 seconds.
Afterwards, the tram reaches *P*_{i} using an auxiliary (slow but safe) engine,
which provides a speed of 5 meters per second
and guarantees no more crashes in *S*_{i}.

For instance, assume that the section length is 300 meters,
and that the current maximum speed is 25 meters per second.
If the driver chooses to travel at 25 *m*/*s*,
the tram will crash for sure.
Since this can happen anywhere between *P*_{i−1} and *P*_{i},
for the sake of computation
we can assume that it will take place exactly in the middle point
(after 150 meters).
Therefore, on the average
the tram will spend 6 seconds to reach the middle point,
10 seconds to recover from the crash,
and 30 seconds to reach *P*_{i},
for a total of 46 seconds.
By contrast, if the tram starts traveling at 15 *m*/*s*,
with probability 0.6
it will crash and spend 10 + 10 + 30 = 50 seconds,
and with probability 0.4
it will reach *P*_{i} after 20 seconds without any crash.
The average time in this case is thus
just 0.6*50 + 0.4*20 = 38 seconds.

When the tram reaches every *P*_{i}, it stops for a few seconds
regardless of having crashed in *S*_{i} or not;
these few seconds (for simplicity, we consider them to be 0)
are enough to (almost) repair the tram:
the maximum speed reduces by 1 *m*/*s* after every crash.
In other words, if we call the initial maximum speed *M*_{0},
then we have *M*_{i} = *M*_{0} − *C*_{i},
where 0 ≤ *C*_{i} ≤ *i*−1 is the total number of crashes
suffered in *S*_{1}, …, *S*_{i−1}.

Write a program to print the optimal average travel time given the initial maximum speed and the length of every section.

[r]

**Input**

Input consists of several cases,
each one with *M*_{0} (a real number between 5 and 1000),
*n* (an integer number between 1 and *M*_{0} − 1),
and the length of every section
(each one a real number between 100 and 1000).

0

**Output**

For every case, print the optimal average travel time with four digits after the decimal point. The input cases have no precision issues.

Public test cases

**Input**

25 1 900 25 2 900 900 25 2 305.15 980.76 5 1 1000

**Output**

102.0000 205.0303 150.0000 210.0000

Information

- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++
- Event
- Segon Concurs de Programació de la UPC - Final
- Date
- 2004-09-29