Barcelona’s trams

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. Di- minishing aesthetic reasons, the Major 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 P0 to a final point Pn visiting the intermediate points P1, ..., Pn−1 in this order. For every 1 ≤ i ≤ n, let Si be the section going from Pi−1 to Pi. Every such section must be traveled at uniform speed vi, which is chosen by the driver at Pi−1. Let Mi be the maximum possible speed of the tram at Si, and assume that the chosen speed is 0 < vi ≤ Mi. Then the probability of crashing in Si is vi/Mi. When a crash happens, the tram uses an efficient recovery system that lasts only 10 seconds. Afterwards, the tram reaches Pi using an auxiliary (slow but safe) engine, which provides a speed of 5 meters per second and guarantees no more crashes in Si. 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 the crash can happen anywhere between Pi−1 and Pi, 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 Pi, 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 Pi 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 Pi, it stops for a few seconds regardless of having had a crash in Si 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. If we call the initial maximum speed M0, then we have Mi = M0 −Ci, where 0 ≤ Ci ≤ i−1 is the total number of crashes suffered in S1, ..., Si−1. Write a program that prints the optimal average travel time given the initial maximum speed and the length of every section. Input Input consists of zero ore more test cases. Each test case consists of a line with M0 (a real number between 5 and 25), n (an integer number between 1 and M0 − 1), and the length of every section (each a real number between 100 and 1000). Output For every test case, print the optimal average travel time with four decimal digits. Sample Input 25 1 900

2/2 25 2 900 900 25 2 305.15 980.76 5 1 1000 Sample Output 102.0000 205.0303 150.0000 210.0000