The Plane Problem
Time Limit: 10 Seconds
Memory Limit: 32768 KB
Air transportability is concerned with the packing of cargo on aircraft. In
order to ensure safe takeoffs and landings, cargo must be packed according to
rigorous rules, which can vary from airplane to airplane. Rules for packing
- All aircraft will have weight limits. They cannot hold more than their weight
limit, and for the sake of efficiency, no plane may carry less than 50% of
its weight limit.
- Cargo items are rectangular and have uniform weight distribution. Two adjacent
items must be at least 1 foot apart to allow for tie downs.
- All aircraft will have a rectangular area for cargo, the cargo hold. No
cargo can be placed within one foot of the edge of the cargo hold to allow
space to tie it down.
- At least 60% of the cargo weight must be put in the front half of the cargo
- The weight on the left side of the center line must be no more than 5% more
or less than the weight on the right hand side of the center line.
- If a piece of cargo can be moved toward the rear of the plane and still
meet the other constraints, then it should be moved toward the rear of the
plane because all loading and unloading takes place at the rear of the plane.
- To allow for speedy loading and unloading, no plane may hold more than 10
You are to write a program to help allocate cargo to aircraft efficiently.
The input will consist of one or more input sets. The first line of each input
set will be an integer 0 <= p <= 10 which represents the number of planes
to be loaded. There will then be p sets of plane information. Each set of plane
information has two lines. The first has a string of 1 to 25 characters representing
the name of the aircraft. No two different aircraft in an input set will have
the same name. The second line will have four integers, 0 < x <= 100,
0 < y <= 30, 0 < w <= 100000, 0 < c <= 20000 where:
- x represents the length of the cargo hold (from the front of the plane to
the rear of the plane) in feet,
- y represents the width of the plane (from left to right) in feet,
- w represents the weight limit of the plane in pounds,
- c represents the cost of the plane in dollars.
After the plane information will be the information about the cargo to be
loaded. The first line will have a single integer 0 < n <= 10, representing
the number of pieces of cargo to be loaded. There will then be n sets of cargo
item information. Each line of cargo information will consist of 4 integers
0 < i <= 1000, 0 < len <= 20, 0 < wid <= 20, 0 < wt <=
- i is a unique value that identifies the cargo item and gives its relative
priority (where the higher the value, the more important the item)
- len is the length of the item in feet
- wid is the width of the item in feet
- wt is the weight of the item in pounds
Items cannot be turned when they are loaded on the aircraft, so the lengthwise
side of the cargo item must be loaded lengthwise along the aircraft. The end
of input will be a set with p = 0. This set should not be processed.
If it is possible to load all of the cargo meeting the constraints, you should
load the cargo using the most inexpensive collection of planes, given the constraints
above. If all of the cargo cannot be loaded, you should load as many items as
possible without regard for cost. If two configurations load the same number
of items, select the configuration with the highest total priority. If two configurations
have the same number of items loaded and the same priority and meet all of the
above constraints, print either one.
The first line of output for each input set should include the number of the
set (starting with 1) and the total cost of the planes used to transport the
set. Then, for each plane used, give the name of the plane on a line by itself
followed by one line for each of the cargo items on the plane (in ascending
numerical order of priority), giving the cargo item number, and the distance
of its leftmost front corner from the front of the cargo hold and the left edge
of the cargo hold (because of the position of tie downs, these must be integer
values). Finally, on the last line of the output, if there are pieces of cargo
that cannot be loaded, list them, in numerical order of priority.
Have a blank line after each input set and use the format in the sample output.
100 30 100000 20000
10 5 1000 200
400 20 20 56000
300 20 20 4000
80 20 10 30000
900 20 10 10000
5 5 3 400
Plane loading 1:
80 loaded at 79 back, 1 from left
300 loaded at 30 back, 5 from left
400 loaded at 9 back, 9 from left
900 loaded at 79 back, 19 from left
Source: Southeast USA 2000