Traffic Jam#1925
The most annoying aspect of traffic jams in large cities is that drivers constantly try to change lanes suddenly in hopes of moving faster. In this problem, you are to determine whether this is a reasonable strategy.
We will consider a relatively simple mathematical model of a traffic jam. Assume there is a road with lanes, numbered from to , and the -th lane moves at speed b_i + a_i \cdot \sin(t + \delta_i) at time . It is always true that b_i > a_i, so the speed is always positive. You may change lanes at any time; changing from lane to lane takes c \cdot |x - y| units of time. During this period, you do not move forward.
Determine the minimal time required to travel a distance , as well as a method of achieving this minimal time. You start at time in lane . You may finish in any lane.
The first line contains two integers and , and a floating-point number (1 \leq N \leq 5, 1 \leq d \leq 1000, 0.001 \leq c \leq 1000). The next lines describe the lanes; each contains two integers a_i and b_i, and a floating-point number \delta_i (0 \leq a_i < b_i \leq 100, 0 \leq \delta_i < 2\pi).
Print the minimal time required to travel the distance on the first line. On the second line, print the number of lane changes required. should not exceed 10^6; it is guaranteed there always exists an optimal strategy requiring at most 10^6 lane changes. On the next lines, print the changes themselves; each line should contain the new lane number and the time at which the lane change is started. The changes must be listed in chronological order. If multiple possible schedules exist, output any of them.
Print all floating-point numbers with maximal possible precision. Your solution will be considered correct if, upon verification, discrepancies do not exceed 10^{-6} (when checking the total distance traveled, or that lane changes do not overlap, etc.). Therefore, it is better to output at least 10-12 digits after the decimal point in each floating-point number.
Example 1