[ Problem C | 1998 ACM Finals problem set | My ACM problem archive | my home page]

Programming Contest World Finals

sponsored by

Flight Planning

Your job is to write a program that plans airplane flights. Each flight consists of a series of one or more legs. Your program must choose the best altitude for each leg to minimize the amount of fuel consumption during the trip.

The airplane has a fixed airspeed, given by the constant VCRUISE, and a most-efficient cruising altitude, AOPT. When flying at altitude AOPT, fuel consumption in gallons per hour is given by GPHOPT. When flying at an altitude that is different from AOPT, fuel consumption increases by GPHEXTRA for each 1000 feet above or below AOPT. The flight starts and finishes at an altitude of 0. Each 1000 foot climb burns an extra amount of fuel given by CLIMBCOST (there is no reduction in fuel consumption when you descend). Make the approximation that all climbing and descending is done in zero time at the beginning of each flight leg. Thus each leg is flown at a constant airspeed and altitude. For this problem, the airplane characteristics are given by the following constants:

VCRUISE | 400 | knots (a knot is one nautical mile per hour) |

AOPT | 30,000 | feet |

GPHOPT | 2000 | gallons per hour |

GPHEXTRA | 10 | gallons per hour for each 1000 feet |

CLIMBCOST | 50 | gallons per 1000 feet of climb |

Before each flight, you are given the length of each leg and the tailwind expected for each leg. A positive tailwind increases the airplane's speed over the ground, and a negative tailwind decreases its speed over the ground. For example, if airspeed is 400 knots and the tailwind is -50 knots, speed over the ground is 350 knots.

By policy, altitude for each leg must be some integer multiple of 1000 feet, between 20,000 and 40,000 feet, inclusive. Your program must compute the best altitude for each leg to minimize overall fuel consumption for the trip, and must compute the fuel required for the trip.

The first input line in a flight contains an integer K (0 < K < 10), representing the number of legs in the flight.The expected tailwind at altitudes between 20,000 and 40,000 feet is computed by linear interpolation. For example, the expected tailwind at 30,000 feet is halfway between the expected tailwind at 20,000 feet and the expected tailwind at 40,000 feet.

The next K input lines each contain the following three integers:

- The length of the leg, in nautical miles
- The expected tailwind at 20,000 feet, in knots
- The expected tailwind at 40,000 feet, in knots

2 2 1500 -50 50 1000 0 0 3 1000 50 0 2000 0 20 1800 -50 100

Flight 1: 35 30 13985 Flight 2: 20 30 40 23983

This page maintained by Ed Karrels.

Last updated September 8, 1999