PROB1: WATER

Determine water allocations.

DESCRIPTION

Capitalists prefer to know who owns things, and water is no exception. Nature recycles a random amount of water each year and places it in various sources (lakes, rivers, and underground aquifers). Contracts for various portions of that water are written.

Unfortunately, there may not be enough water available in a drought year to fulfill each contract. The resolution to this is via priorities. The highest priority contracts are fulfilled before the next tier of priorities. If there is insufficient water to fulfill the requirements of all the contracts of a given priority, what remains of the water source is divided proportionally among all the contracts of that priority.

For example, suppose a water source has 1,000,000 (one million) cubic feet of water available in a given year. That water source has the following requirements:

Name	Priority	Requirement
A	1	500,000
B	1	250,000
C	2	700,000
D	2	300,000
E	3	100,000

The allocation for that year would be that contract A and B get full allotments. Contracts C and D divide the remainder proportionally: C's contract represents 70% of the contracts with priority 2, and D's contract represents the other 30%. Thus C would obtain 70% of the remaining 250,000 cubic feet of water, or 175,000 cubic feet of water, and D would be allocated the remainder (30% of 250,000 cubic feet, or 75,000 cubic feet). The lower priority contract E would be allocated no water.

In this problem you are to calculate water allocations for various sources.

INPUT: prob1.dat

The input file will contain a sequence of one or more allocation problems. Each allocation problem will have a first line describing the source, followed by one or more lines describing the contracts on that source.

The first line of an allocation problem has the form


"SOURCE_NAME",SOURCE_VOLUME


The SOURCE_NAME will be a string of no more than 80 printable ASCII characters. It will be enclosed by double quotes but not contain any double quotes. The SOURCE_VOLUME will be an integer no more than 1 trillion: 1000000000000. White space may appear on the line, and, unless inside the quoted name, should be ignored. If SOURCE_NAME is "END", then this indicates no more allocation problems are present in the input file and your program should not process any further data.

Following a line indicating another source, there will be zero or more allocations of that source. These are lines of the form


"CONTRACT_NAME",CONTRACT_PRIORITY,CONTRACT_VOLUME


The CONTRACT_NAME will be a string of no more than 80 printable ASCII characters. It will be enclosed by double quotes but not contain any double quotes. The CONTRACT_PRIORITY will be a positive integer with magnitude no larger than 1000. The CONTRACT_VOLUME will be a non-negative integer no more than 1 trillion. White space may appear on the line, and, unless inside the double quotes, should be ignored. If CONTRACT_NAME is "END", then this indicates no more contracts are present for this source.

Note that CONTRACT_PRIORITY will be a non-decreasing sequence for each allocation problem.

An example input file would be

       column   111111111122222222223
       123456789012345678901234567890
line 1:"Le River",1000000[EOL]
     2:  "People",1,500000[EOL]
     3:  "Farms",1,250000[EOL]
     4:  "Mine",2,700000[EOL]
     5:  "Golf Course",2,300000[EOL]
     6:  "Car Wash",3,100000[EOL]
     7:  "END",0,0[EOL]
     8:"Le Lake",1000000[EOL]
     9:  "A",1,500000[EOL]
    10:  "B",1,250000[EOL]
    11:  "D",2,300000[EOL]
    12:  "E",3,100000[EOL]
    13:  "END",-1,0[EOL]
    14:"END",0[EOL]
      :[EOF]

OUTPUT: prob1.out

The output file has a format similar to the input file. The differences are that

• No additional whitespace is allowed.
• In the place of CONTRACT_VOLUME, you should instead report CONTRACT_AWARD, which is the actual volume awarded to the contract (truncated to its integer part).
• The end of a list of contracts is indicated by the line
"END",0,0
• The end of the list of allocation problems is indicated by the line
  "END",0

The correct output corresponding to the example input file would be

       column   111111111122222222223
       123456789012345678901234567890
line 1:Program 1 by team 0[EOL]
     2:"Le River",1000000[EOL]
     3:"People",1,500000[EOL]
     4:"Farms",1,250000[EOL]
     5:"Mine",2,175000[EOL]
     6:"Golf Course",2,75000[EOL]
     7:"Car Wash",3,0[EOL]
     8:"END",0,0[EOL]
     9:"Le Lake",1000000[EOL]
    10:"A",1,500000[EOL]
    11:"B",1,250000[EOL]
    12:"D",2,250000[EOL]
    13:"E",3,0[EOL]
    14:"END",0,0[EOL]
    15:"END",0[EOL]
    16:End of program 1 by team 0[EOL]
      :[EOF]