Water Allocation
A. First Edition
This is the first problem of a code contest and I am frustrated at the fact that I cannot even finish the very
first problem within three hours.
Determine water allocations.
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.
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]
The output file has a format similar to the input file. The differences are that
"END",0,0
"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]
At first, I didn't notice the problem of double quotes which is quite annoying. I really dislike "fstream" as it
can only do the very simple job and for the more detailed job, you have to use "FILE" pointer.
Then, I repeatedly forget to initialize all data of "states" such as "rank", "requires"... which cost me another
half hour for debugging, maybe longer than that?
There are few points to mention.
E.Further improvement
F.File listing
1. water.cpp
file name: water.cpp
#include <iostream>
#include <fstream>
using namespace std;
const int MaxNameLength=80;
const int MaxContractors=30;
struct Contractor
{
char name[MaxNameLength];
int priority;
long quota;
long allocated;
};
//end is the bound of ending, exclusive
void allocate(int start, int end, long curVol, long requires);
void readName(char* buffer);
//void readNumber(int& number);
void readNumber(long& number);
Contractor groups[MaxContractors];
char buffer[MaxNameLength];
FILE* in;
int main()
{
char resource[MaxNameLength];
//bool newStart=false;
long totalVolume=0;
int rank=1;
long requires=0;
long curVol;
int index=0, start=0;
ofstream out;
in=fopen("prob1.dat", "r");
out.open("prob1.out", ios::out);
out<<"program 1 by team "<<0<<"\n";
while (!feof(in))
{
readName(resource);
//fscanf(in, "%d,", totalVolume);
if (strcmp(resource, "\"END\"")==0)
{
break;
}
readNumber(totalVolume);
//in>>resource;
//in>>totalVolume;
curVol=totalVolume;
while (!feof(in))
{
readName(groups[index].name);
if (strcmp(groups[index].name, "\"END\"")!=0)
{
//fscanf(in, "%,d,", groups[index].priority);
readNumber((long&)groups[index].priority);
//fscanf(in, "%,d\n", groups[index].quota);
readNumber(groups[index].quota);
if (groups[index].priority>rank)
{
allocate(start, index, curVol, requires);
curVol-=requires;
if (curVol<0)
{
curVol=0;
}
requires=groups[index].quota;
start=index;
rank=groups[index].priority;
index++;
}
else
{
requires+=groups[index].quota;
index++;
}
}
else
{
allocate(start, index, curVol, requires);
break;
}
}
out<<resource<<" , "<<totalVolume<<"\n";
for (int i=0; i<index; i++)
{
out<<groups[i].name<<" ,"<<groups[i].allocated<<"\n";
}
index=0;
start=0;
rank=1;
requires=0;
}
return 0;
}
void readNumber(long& number)
{
char buffer[MaxNameLength];
char ch;
int index=0;
bool started=false;
while (!feof(in))
{
if (started)
{
if (ch>='0'&&ch<='9')
{
buffer[index++]=ch;
}
else
{
buffer[index]='\0';
break;
}
}
if (!started&&ch<='9'&&ch>='0')
{
buffer[index++]=ch;
started=true;
}
ch=fgetc(in);
}
number=atoi(buffer);
}
void readName(char* buffer)
{
int index=0;
char ch;
bool started=false;
ch=fgetc(in);
while (!feof(in))
{
if (started)
{
if (ch=='"')
{
buffer[index++]=ch;
buffer[index]='\0';
break;
}
else
{
buffer[index++]=ch;
}
}
if (!started&&ch=='"')
{
index=0;
started=true;
buffer[index++]=ch;
}
ch=fgetc(in);
}
}
void allocate(int start, int end, long curVol, long requires)
{
bool percent;
percent=requires>curVol;
for (int i=start; i<end; i++)
{
if (curVol>0)
{
if (percent)
{
groups[i].allocated=curVol*((double)groups[i].quota/requires);
}
else
{
groups[i].allocated=groups[i].quota;
}
}
else
{
groups[i].allocated=0;
}
}
}
The input file "prob1.dat" is like following:
"Le River",1000000 "People",1,500000 "Farms",1, 250000 "Mine",2,700000 "Golf Course",2,300000 "Car Wash", 3,100000 "END",0,0 "Le Lake",1000000 "A",1,500000 "B",1,250000 "D",2,300000 "E",3,100000 "END",-1,0 "END",0
The result is like following:
program 1 by team 0 "Le River" , 1000000 "People" ,500000 "Farms" ,250000 "Mine" ,175000 "Golf Course" ,75000 "Car Wash" ,0 "Le Lake" , 1000000 "A" ,500000 "B" ,250000 "D" ,250000 "E" ,0