Problem 111: Chicken Soup
(U.M. ACM Runoffs 2002, problem 4)
Description
The Acme Chicken Soup Company
makes two varieties of chicken soup: Captain Clucky's Crispy Chickeny
Super Soup (hereafter referred to as A), and Madame Beauregarde's
Potage de Poulet de Luxe (referred to as B). The recipes for the two
varieties are exactly the same except for the amounts of two special
ingredients, Frankincense and Myrrh. Each gallon of A requires FA grains
of frankincense and MA grains of myrrh; each gallon of B requires FB
grains of frankincense and MB grains of myrrh; in case you were wondering,
a grain is a real unit of measurement, there are 437½ grains in an ounce.
The quantities FA, MA, FB, and MB are kept secret, and will be provided
as inputs to your program while you are not looking.
Each day the company buys the
day's supply of frankincense and myrrh from its suppliers. They are rare
substances, so there are limits to the amount available: no more than
Fmax grains of frankincense and Mmax grains of myrrh. The price of
frankincense is PF cents per grain, and of myrrh PM cents per grain.
The only other ingredient is recycled scum, which costs nothing.
Acme is contractually obliged
to supply its customer with at least Amin gallons of A and Bmin gallons
of B per day, and the prices are set at PA cents per gallon of A, and PB
cents per gallon of B.
Your job is to write a program
that uses the parameters FA, MA, FB, MB, Fmax, Mmax, PF, PM, Amin, Bmin,
PA, PB, to work out how much A and B to make each day in order to maximise
profits. If QA and QB represent the quantity of A and B made, in gallons,
and QF and QM represent the quantity of frankincense and myrrh used, in
grains, then the profit is simply defined as the price of the product
minus the cost of the ingredients:
Profit = (QA×PA+QB×PB)-(QF×PF+QM×PM)
The input will be a series of
lines each containing 12 floating point numbers, being the input
parameters in the order listed above. There should be one line of
output for each line of input, it should contain the calculated quantities
QA, QB, QF, and QM in that order, followed by the profit in cents, all
rounded to two digits after the decimal point. The inputs will be terminated
by a line containing two zeros. You may rest assured that none of the inputs
will ever be negative or zero. If there is more than one optimal solution,
all equally good solutions will be accepted. If it is not possible to meet
Acme's contractual obligations, the output should be just the word "Impossible".
Sample Input
1 1 1 1 1000 100 1 1 10 10 600 300
1 1 1 1 1000 100 800 1 10 10 600 300
1 1 1 1 1000 100 1 1 10 10 600 30
1 1 1 1 10 10 1 1 20 20 600 30
0 0
Sample Output
90.00 10.00 100.00 100.00 56800.00
10.00 10.00 20.00 20.00 -7020.00
90.00 10.00 100.00 100.00 54100.00
Impossible
End of Problem