code contest

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.

    B.The problem

#### 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]

`

¡¡

¡¡

C.The idea of program
¡¡

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?

    D.The major functions

    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

    ¡¡