Cod sursa(job #441176)

Utilizator DarkHunterjCont cu nume gresit sau fals DarkHunterj Data 12 aprilie 2010 20:01:20
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 1.74 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct gutui
{
	int size;
	int weight;
}Gutue;

int rule(const void * a, const void *b)
{//order by weight then size
	Gutue * A =(Gutue *)a;
	Gutue * B =(Gutue *)b;
	if(A->weight > B->weight)
		return -1;
	else if(A->weight < B->weight)
		return 1;
	else
		return A->size-B->size;
}

int insert(int weight,int size,int *vect)
{//insert weight in a vector at position size, or at an available lower position, if no position is available return 0 otherwise return weight
//if it returns 0 it means the "gutuie" can't be taken... because it reached maximum size
	if(vect[size]==0)
	{
		vect[size]=weight;
		return weight;
	}
	else
	{
		while(size>=0)
		{
			if(vect[size]==0)
			{
				vect[size]=weight;
				return weight;
			}
			size--;
		}
		return 0;
	}
}

int main(int argc, char **argv)
{
	int H, aux, min, dif, U, n, i, total=0;
	int *vect;
	FILE * in = fopen("gutui.in","rt");
	FILE * out = fopen("gutui.out","wt");
	
	//Read data
	fscanf(in,"%i %i %i",&n,&H,&U);
	Gutue *gut = (Gutue *) malloc(sizeof(Gutue) * n);
	min=H/U;
	dif=H%U;
	for(i=0;i<n;i++)
	{
		fscanf(in,"%i %i",&(gut[i].size),&(gut[i].weight));
		if(gut[i].size>H)
		{//eliminate unreachable
			i--;
			n--;
		}
		else
		{//calculate level
			if(gut[i].size%U>dif)
				gut[i].size+=U;
			gut[i].size/=U;
			if(gut[i].size<min)
				min=gut[i].size;
		}
	}
	H++;
	H/=U;
	//Read data
	
	qsort(gut,n,sizeof(Gutue),rule);//sort by rule, see above
	
	vect=(int*) malloc(sizeof(int)*(H-min+1));
	
	for(i=0; i<(H-min+1);i++)
	{//make sure the vector has 0s
		vect[i]=0;
	}
	
	for(i=0; i<n; i++)//for all the "gutui" that can be taken add there weight
		total+=insert(gut[i].weight,H-gut[i].size,vect);
	
	fprintf(out,"%i\n",total);
	
	fclose(in);
	fclose(out);
	return 0;
}