Not an official ACM page
[ Problem C | 1998 ACM Finals problem set | My ACM problem archive | my home page]
The 1998 22nd Annual acm International Collegiate
Programming Contest World Finals
sponsored by IBM


Problem B
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.

Input

The first line contains an integer N, representing the number of flights you are required to plan. Each flight consists of the following input lines:
The first input line in a flight contains an integer K (0 < K < 10), representing the number of legs in the flight.
The next K input lines each contain the following three integers:
  1. The length of the leg, in nautical miles
  2. The expected tailwind at 20,000 feet, in knots
  3. The expected tailwind at 40,000 feet, in knots
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.

Output

Your program must produce one output line for each flight. The output line must contain the flight number (counting from the beginning of the problem), the chosen altitude for each leg (in thousands of feet), and the fuel required for the trip (in gallons, to the nearest gallon).

Sample Input

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

Output for the Sample Input

Flight 1: 35 30 13985
Flight 2: 20 30 40 23983
This page maintained by Ed Karrels.
Last updated September 8, 1999