NOI '12 P2 - Highway Cycling

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 0.6s
Memory limit: 512M

Problem type
National Olympiad in Informatics, China, 2011

DanDan is always interested in challenging himself. This summer, he prepares to cycle along the Sichuan-Tibet highway to reach Lhasa. It is widely known that the Sichuan-Tibet Highway is filled with hauntingly beautiful scenery, but also happens to contain many dangerous obstacles. DanDan's physical abilities are very limited, so before every day of cycling, he will plan his destination ahead of time. Appropriately distributing the workload is a very critical matter.

DanDan has a cutting-edge bicycle. Riding it, the only thing he has to worry about is air resistance (he will not at all be affected by the friction of the bicycle, nor the friction between the bicycle and the ground). One day, he decided to cycle N sections of road. All of the road in any given section can be considered identical. For the i-th section, we assign three parameters s_i, k_i, and v'_i. Here, s_i represents the length of the road, k_i represents the coefficient of air resistance, and v'_i represents the velocity of the wind on that section of road (v'_i > 0 indicates that the wind is blowing in the direction being traveled, while the opposite means that the wind is blowing against the direction being traveled). At a given moment, if the bicycle travels at a velocity of v, then the force of air resistance it experiences is F = k_i \times (v - v'_i)^2. This way, if a section of road of length s was traveled at a constant velocity of v, then the energy consumed (work done) is E = k_i \times (v - v'_i)^2 \times s.

Let E_U represent DanDan's initial energy at the start of the day. Please help him devise a cycling plan such that he arrives at his destination as soon as possible. DanDan would like to know the value of the shortest possible time T.

Input Specification

The first line of input contains a positive integer N and a real number E_U, respectively representing the number of road sections and DanDan's initial energy.
For the following N lines, each line will describe a single road section. Each line contains 3 real numbers s_i, k_i, and v'_i, respectively representing the i-th road section's length, coefficient of air resistance, and wind velocity.

Output Specification

Output a single real number T to at least 6 decimal places, representing the minimum time it will take for DanDan to reach his destination. Your answer will be considered correct if it differs from the actual answer by no more than 10^{-6}.

Sample Input

3 10000
10000 10 5
20000 15 8
50000 5 6

Sample Output

12531.34496464

Explanation

One valid way is to ride uniformly on each section of road. The speeds are respectively 5.12939919, 8.03515481, and 6.17837967.

Constraints

For 10\% of the test cases, N = 1.
For 40\% of the test cases, N \le 2.
For 60\% of the test cases, N \le 100.
For 80\% of the test cases, N \le 1\,000.
For all of the test cases, N \le 10\,000, 0 \le E_U \le 10^8, 0 < s_i \le 100\,000, 0 < k_i \le 15, and -100 < v'_i < 100. It is guaranteed that answers will not exceed 10^5.

Hint

There will always exist an optimal method where DanDan rides with uniform velocity on all sections.

Problem translated to English by Alex.


Comments

There are no comments at the moment.