For the Porsche
Time Limit: 10 Seconds
Memory Limit: 32768 KB
The Cash Cow Consulting Company is challenging the Vice Presidents to increase
the profitability of their departments. In an effort to provide proper incentive,
the Vice President whose department has the highest Profitability Index (PI)
will win a brand new Porsche. The contest rules are as follows:
. The winning department will have the maximum Profitability Index (sales /
. Each department must stay within the minimum and maximum cost range.
. In the case of equal profitability indexes, the higher profit margin will
win (sales - development cost).
. If two departments are still tied, the winning department will develop the
smaller number of features.
. If two departments are still tied, the winning department will satisfy the
Mike Miser is still driving his high school moped and has determined this is
his chance to upgrade. He has instructed the engineering department to determine
what it will cost for each feature to be developed. He then instructed the sales
force to determine what features each customer requires, and what sales that
will generate. (To make a sale to a customer all features required must be provided).
Mike will then determine which feature combination his division should complete
to maximize his chances of winning the contest.
1. Because of the type of product the Cash Cow Consulting Company creates, the
production costs are negligible, and do not need to be considered. Only the
development costs should be considered.
2. The tie breakers listed will result in the selection of exactly one feature
3. At least one feature set will satisfy the requirements.
4. The Profitability Index should be rounded to three decimal places. The values
3.4566 and 3.4574 will be considered equal.
All input will be positive integers.
The first line of input will indicate the number of data sets.
The first line of each data set will contain 4 integers separated by white-space.
In order they are the minimum cost, maximum cost, number of potential features
(N) and number of potential customers (M). N and M will be no larger than 20.
The next N lines (one for each feature) indicate the cost of each feature.
The next M lines will contain the following (one line for each customer):
Number of required features Feature number (for each required feature) Total
Sales for that customer.
For instance, if a given customer wanted 3 features, number 1,2 and 5 and would
provide sales of 50, the line would read: "3 1 2 5 50"
The next data set, if more remain, will begin on the next line.
The first line of output for each data set should indicate which Feature Set
is being considered. These should print "Feature Set N" where N is the feature
set number, counting from 1.
The next line of output for each data set should indicate the profitability
index to 3 decimal places.
The next line of output for each data set should indicate the sales dollars
The next line of output for each data set should indicate the cost
The next line of output for each data set should indicate which features are
The first feature is feature number 1. They must be listed in order, white-space
The final line of output for each data set should indicate the customers who
were satisfied. The first customer is customer #1. They must be listed in order,
No extra output should appear.
100 2000 7 6
4 1 4 5 6 4000
4 1 4 5 6 500
4 1 4 5 6 60
3 1 4 5 7
4 1 2 3 5 5
4 1 2 3 7 6
Feature Set 1
1 4 5 6
1 2 3 4
Source: Mid-Atlantic USA 2001