Deciding the optimum number of pit stops in a Formula One race is not a trivial matter. The problem is greatly influenced by many factors: the length of the circuit and the total number of laps, the time lost in each pit stop, the maximum tank capacity of the car, the fuel consumption per kilometer, the relationship between speed and current weight of the fuel, etc. You have been hired by the prestigious F1 team SlowCheapCars in order to decide their optimum pit stops strategy. Help them to win the race. Each time we do a pit stop, some precious seconds are lost. In particular, there are two components: • A constant time, G, due to slowing down, stopping, and accelerating back up to normal speed; and • A variable quantity, x∗H, depending on the number of litres added to the tank (x) and the speed of the highly pressurized refueling system (H, in seconds/litre). Besides, the average speed of the car per lap is not constant; on the contrary, it depends on the fuel load at a given moment. When the tank is full, the car is normally slower because of its total weight. But when it is almost empty, the car is able to go faster. This variation is given by the number of seconds gained per lap when the fuel load is reduced 10 litres, F (in seconds per 10 litres). For example, let E be the time to complete a lap starting with the full tank, and let D be this maximum capacity of the tank; if the current fuel load is D − 20 litres, the lap time will be: E − 2F . The initial fuel load of the car is given by C (in litres). However, according to a recent regulation by the F.R.I.A., we have the possibility to start the race from the pit line; in that case, we are free to decide the initial fuel load, at the expense of losing I seconds in the first lap. Some other parameters of the problem are the total number of laps of the race, A, the length of the circuit, B (in kilometers), the fuel consumption per lap, J, and the name of the circuit, N. A pit stop strategy is given by the number of stops and the decision whether to start or not from the pit line. We want to obtain the optimum strategy of pit stops in a given circuit, that is, the one that produces the minimum total time to complete the A laps. Obviously, the fuel load of the car can never be below 0. Input The first line of the input contains an integer M, indicating the number of test cases. For each test case, there are the following lines (the text in typewriter appears literally): Circuit N AB Fuel CD Speed EF Pit stop GHI Consumption J Where:
2/4 A : number of laps of the race (from 1 to 100). Integer. B : length of the circuit, i.e., kilometers per lap. Real with 2 decimal digits. C : initial fuel in the tank of the car, in litres (from 1 to 200). Integer. D : maximum capacity of the tank of the car, in litres (from 1 to 200, and 0 ≤ C ≤ D). Integer. E : number of seconds per lap starting the lap with the full tank. Real with 2 decimal digits. F : number of seconds per lap gained for each reduction of 10 litres in fuel load. Real with 1 decimal digit. It could be negative. G : constant time lost in each pit stop, in seconds. Real with 2 decimal digits. H : seconds per litre lost in the pit stop to refuel the car. Real with 2 decimal digits. I : seconds lost in the first lap if we decide to start from the pit line. Real with 2 decimal digits. J : litres of fuel consumed per lap (it is supposed to be independent of the speed, and J ≤ D). Integer. N : the name of the circuit. String. Observe that fuel is always considered to be an integer value, while time is given in seconds with 2 decimal digits (rounding is not required in this problem). Output For each test case, the output should contain the following lines (the text in typewriter must appear literally): Circuit N Estimated time T Initial fuel K Pit stops S Where: T : estimated time (in seconds) to complete the A laps of the race using the optimum strategy. Real with 2 decimal digits. K : initial fuel load; if K is not equal to C, it means that we start the race from the pit line. Integer. S : optimum number of pits stops. Integer. You can suppose that the solution always exists and is unique. Sample Input 4 Circuit of Monte Carlo 78 3.34 Fuel 70 160 Speed 79.22 0.3 Pit stop 24.51 0.11 18.54 Consumption 4
3/4 Circuit of Hockenheim 67 4.57 Fuel 60 180 Speed 81.32 0.3 Pit stop 22.81 0.09 21.33 Consumption 5 Circuit of Valencia 57 5.44 Fuel 57 150 Speed 72.32 0.2 Pit stop 22.01 0.13 20.12 Consumption 5 Circuit of Moon Park 60 6.21 Fuel 10 160 Speed 76.32 -0.3 Pit stop 10.00 0.26 15.25 Consumption 6 Sample Output Circuit of Monte Carlo Estimated time 6002.41 Initial fuel 70 Pit stops 3 Circuit of Hockenheim Estimated time 5271.32 Initial fuel 60 Pit stops 3 Circuit of Valencia Estimated time 4087.14 Initial fuel
4/4 57 Pit stops 2 Circuit of Moon Park Estimated time 4763.39 Initial fuel 160 Pit stops 4