Barcelona's trams P38716


pdf   zip


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 P0 to a final point Pn visiting the intermediate points P1, …, Pn−1 in this order. For every 1 ≤ in, let Si be the section that goes from Pi−1 to Pi. Every such section must be travelled 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 < viMi. 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 this 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 crashed 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. In other words, if we call the initial maximum speed M0, then we have Mi = M0Ci, where 0 ≤ Cii−1 is the total number of crashes suffered in S1, …, Si−1.

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



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



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


  • Information
    Salvador Roura
    Official solutions
    User solutions