1 Problem 99
Saint Bonaventure University
Thirteenth Annual Invitational
High School Programming Contest
Sample Problem (using classes)
Problem 99: Sitting by the Dock of the (loading) Bay
Overview:
One of the industries in which labor unions are most entrenched is the shipping industry. It is often the case that management can control what packages are shipped to where but now how the packages are loaded onto or unloaded from the trucks. In this problem, you will simulate the task of a company’s management as you solve a version of the computer science chestnut known as Bin Packing.
Problem:
You are to simulate the job of a corporate manager who must arrange for a series of packages to be shipped from “here” to “there”. To keep costs down, you cannot store packages for any appreciable amount of time. You must load the packages onto trucks as soon as (i.e. in the order that) they arrive. In a similar vein, you wish to use as few trucks as possible. Unfortunately, due to the constraint of labor unions, however, you cannot directly control which package goes on which truck. In fact, you may interact with the trucks only by giving commands to the union boss. This scenario is implemented via the LoadingBay class. You should examine bay.h to learn the syntax (and complete list) of the permitted commands.
Conceptually, a loading bay consists of two parking spaces for trucks. When a package is to be loaded, the union workers place it on whichever truck they like. There is no predicting how they will do this except that you know that they will always place it on one of the trucks if this is possible. If it is not possible for them to place the package, they will so inform you and you must dismiss one of the trucks. (You should always dismiss the truck with the least remaining capacity.) When you have no more packages, you should dismiss any non-empty trucks.
Side note: All trucks have a capacity of at least 10 and all packages have size no more than 10; therefore all packages fit into any empty truck.
Input:
The input will consist of sequence of integers (between 1 and 10 inclusive) representing (in order of arrival/loading) the size of each package. The value of –1 will be used to indicate that there are no more packages.
- over -
Output:
The output is a single line of text stating the number of trucks needed for this particular ordering of packages, in the form demonstrated in the sample output.
Example 1:
Input
8 2 3 6 5 4 2 7 5 -1
Output
3 trucks were used.
Example 2:
Input
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
-1
Output
13 trucks were used.