main.c

ACM比赛的成绩计算方法

/**************************************************
*FILE:MAIN.c                                      *  
*Function to Review of Programming Contest Result *
*Written by Chen Sai 2006.1.7                     *
**************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct contest *conRes;
typedef conRes point; 

struct contest
{
	/*Declare the data structure of the contest*/
	char name[22];
	int time;
	int extratime;
	int flag;
};

int totaltime;        /*the time totally spent*/
int order[10];
int timelimited;      /*the time limit of the contest*/ 
int number;
int readtime;         /*the time spent in reading the contests*/
int solvedcontestnum; /*the number of the contests solved*/

int solve(point solvedcontest[])
{
	/*define some variable*/
	int marker[10][10];
	int depth;/*the serial number of the contest solved*/
	int m,n,time;
	int cost;
	int tmporder[10];/*the number of the contests solved before*/
	int times[10];/*times of debugging program*/
    /*Initialize the variables*/
	depth=0;
	time=readtime;
	cost=0;
    /*Initialize some arrays*/
	for(m=0;m<10;m++)
	{
		tmporder[m]=-1;
		times[m]=0;
	}
	for(m=0;m<10;m++)
		for(n=0;n<10;n++)
			marker[m][n]=0;

	if(number==1)
	{   /*the condition there is only one contest here*/
		times[0]=(time+solvedcontest[0]->time-1)/60;/*count the times debugging the programme*/
		time+=solvedcontest[0]->time+times[0]*solvedcontest[0]->extratime;/*count the time spent in solving the contest*/
		cost+=time+times[0]*20;/*count the total time consumed for the contest*/
		if(cost<=timelimited)
		{/*the time cosumed for the contest isn't beyond the limite*/
			order[0]=0;
			totaltime=cost;
			return 0;
		}
		else
			return 0;
	}
	while(depth>=0)
	{/**/
		if(number>depth&&timelimited>=time)
		{/*the depth and the time is under the limit*/
			for(n=0;n<number;n++)
				if(solvedcontest[n]->flag==0&&marker[depth][n]==0)
				{
					marker[depth][n]=1;/*mark this point*/
					solvedcontest[n]->flag=1;
					times[depth]=(time+solvedcontest[n]->time-1)/60;
					time+=solvedcontest[n]->time+times[depth]*solvedcontest[n]->extratime;
					cost+=time+times[depth]*20;
					tmporder[depth++]=n;/*one more contest has been solved*/
					break;
				}
			if(n==number&&depth==0)
				break;
			else if(n==number)
			{   /*Backtracing*/
				depth--;
				m=tmporder[depth];
				cost=cost-time-times[depth]*20;
				time=time-solvedcontest[m]->time-times[depth]*solvedcontest[m]->extratime;
				solvedcontest[m]->flag=0;
				tmporder[depth]=-1;
				for(m=0;m<10;m++)
					marker[depth+1][m]=0;
				if(depth>solvedcontestnum||(depth==solvedcontestnum&&cost<totaltime))
				{
					for(m=0;m<depth;m++)
						order[m]=tmporder[m];
					totaltime=cost;
					solvedcontestnum=depth;
				}
				
			}
		}
		else if(depth==number&&time<=timelimited)
		{/**/
			if(depth>solvedcontestnum||(depth==solvedcontestnum&&cost<totaltime))
			{
				for(m=0;m<depth;m++)
					order[m]=tmporder[m];
				totaltime=cost;
				solvedcontestnum=depth;
			}
			depth--;
			m=tmporder[depth];
			cost=cost-time-times[depth]*20;
			time=time-solvedcontest[m]->time-times[depth]*solvedcontest[m]->extratime;
			solvedcontest[m]->flag=0;
			tmporder[depth]=-1;
		}
		else if (depth!=0)
		{
			depth--;
			m=tmporder[depth];
			cost=cost-time-times[depth]*20;
			time=time-solvedcontest[m]->time-times[depth]*solvedcontest[m]->extratime;
			solvedcontest[m]->flag=0;
			tmporder[depth]=-1;
			for(m=0;m<10;m++)
				marker[depth+1][m]=0;
			if (depth>solvedcontestnum||(depth==solvedcontestnum&&cost<totaltime))
			{
				for(m=0;m<depth;m++)
					order[m]=tmporder[m];
				totaltime=cost;
				solvedcontestnum=depth;
			}
				
		}
		else
			break;
	
	}
	
	
}

main()
{   /*define some variable*/
	FILE *input, *output;
	int  hour,i,k,m;
	point solvedcontest[10];

	/*Open the file output.txt with write form*/
	output=fopen("output.txt","w");
	i=0;
	while((input=fopen("input.txt","r"))==NULL)/*Open the input.txt with read form*/
	{
		printf("Cannot open the input.txt file!\n");/*Print "cannot open this file" if cannot open the "input.txt" file*/
		exit(1);
	}
	fscanf(input, "%d", &hour);/*get the number of time limit*/

	while(hour>0)
	{
		timelimited=hour*60;/*turn the unit of the limited time from hour into minute*/
		totaltime=0;
		solvedcontestnum=0;
		for(i=0;i<10;i++)
		{   /*creat space for the structure */
			solvedcontest[i]=(point)malloc(sizeof(struct contest));
		}
		for(i=0;i<10;i++)
		{   /*Initialize the structure solvedcontest and the order*/
			order[i]=-1;
			solvedcontest[i]->extratime=0;
			solvedcontest[i]->time=0;
			solvedcontest[i]->flag=-1;
			for(k=0;k<22;k++)
				solvedcontest[i]->name[k]='\0';
		}
		fscanf(input,"%d",&number);/*get the number of the contests*/
		fscanf(input,"%d",&readtime);/*get the number of the readtime*/
		for(i=0;i<number;i++)
		{/*get the number for the element in the structure*/ 
			fscanf(input,"%s",solvedcontest[i]->name);
			fscanf(input,"%d",&(solvedcontest[i]->time));
			fscanf(input,"%d",&(solvedcontest[i]->extratime));
			solvedcontest[i]->flag=0;
		}
		solve(solvedcontest);/*run the solve*/
		fprintf(output,"Total time=%d\n",totaltime);/*put out the total time consumed for all contests*/
		for(m=0;order[m]>=0&&m<9;m++)
			fprintf(output,"%s\n",solvedcontest[order[m]]->name);/*put the names of contests solved in order*/
		fprintf(output,"\n");
		for(i=0;i<10;i++)
			free(solvedcontest[i]);
		fscanf(input,"%d",&hour);
	}
	fclose(input);
	fclose(output);
}