FlightScheduler
SRM 347 · 2007-05-01 · by StevieT
SRM 347 · 2007-05-01 · by StevieT · Math, Search
Problem Statement
Problem Statement
The Breguet range equation tells us how far an aircraft can fly if it has a given mass of fuel on board. It states that the maximum range of an aircraft R is given by:
R = K * ln(take-off mass / empty mass)
where K is a constant for the aircraft and the take-off mass is equal to the empty mass + the mass of fuel on board the aircraft. In addition, taking off and gaining altitude takes a certain, constant amount of fuel.
An airline wishes to minimize the amount of fuel consumed on a given journey by allowing the aircraft to stop at intermediate cities along the way to refuel. Assume that the aircraft can stop an unlimited number of times and can stop at any point of its journey. Also assume that it can carry an unlimited amount of fuel.
You will be given anint distance, the total distance of the journey, the int value K for the aircraft, an int emptyMass containing the empty mass of the aircraft and an int takeoffFuel containing the additional mass of fuel required each time the aircraft takes off. You should return a double containing the minimum amount of fuel required to complete the journey.
R = K * ln(take-off mass / empty mass)
where K is a constant for the aircraft and the take-off mass is equal to the empty mass + the mass of fuel on board the aircraft. In addition, taking off and gaining altitude takes a certain, constant amount of fuel.
An airline wishes to minimize the amount of fuel consumed on a given journey by allowing the aircraft to stop at intermediate cities along the way to refuel. Assume that the aircraft can stop an unlimited number of times and can stop at any point of its journey. Also assume that it can carry an unlimited amount of fuel.
You will be given an
Notes
- The return value must be accurate to within an absolute or relative tolerance of 1e-9.
Constraints
- distance will be between 1 and 200,000, inclusive.
- K will be between 1 and 200,000, inclusive.
- emptyMass will be between 1 and 200,000, inclusive.
- takeoffFuel will be between 1 and 200,000, inclusive.
Examples
0)
40000 100000 150000 5000 Returns: 76420.82744805096
The optimal schedule here is to make 1 stop right in the middle of the flight.
1)
40000 55000 150000 5000 Returns: 138450.61724934017
K is a measure of the efficiency of the aircraft. With this less efficient aircraft it's best to stop twice.
2)
1000 500 1000 50 Returns: 2664.9853821314487
3)
10000 100 200 5 Returns: 24635.869665316768
4)
100000 50 600 2 Returns: 1299304.0427867468
Submissions are judged against all 50 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class FlightScheduler with a public method double minimizeFuel(int distance, int K, int emptyMass, int takeoffFuel) · 50 test cases · 2 s / 256 MB per case