Cod sursa(job #437060)

Utilizator shadizarVirjoghe Razvan shadizar Data 9 aprilie 2010 11:48:36
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 1.31 kb
#include <stdlib.h>
#include <stdio.h>


typedef struct gutuie {

	int inaltime;
	int greutate;
	float prioritate;
	int level;
} Gutui;


int comp(const void *a, const void *b)
{

	Gutui *ia = (Gutui *)a;
	Gutui *ib = (Gutui *)b;
	return (ia->prioritate < ib->prioritate);

} 


int main()
{
	
	int H,U,MASA=0;
	long i,N,l,k=0,max_level=0,j;
	FILE *f;
	f=fopen("gutui.in","r");

	fscanf(f,"%ld",&N);
	fscanf(f,"%d",&H);
	fscanf(f,"%d",&U);
		
	Gutui *G;
	G=(Gutui*)malloc(N*sizeof(Gutui));
	
	for (i=0;i<N;i++)
	{
		fscanf(f,"%d",&G[i].inaltime);	
		fscanf(f,"%d",&G[i].greutate);
	}
	
	
	for (i=0;i<N;i++)
	{
		G[i].level = (H-G[i].inaltime)/U+1;
		G[i].prioritate = (float)G[i].greutate/(float)G[i].level;
		if (G[i].level > max_level)
			max_level = G[i].level;	
	}
	
	int *V;
	V=(int*)calloc(max_level,sizeof(int));

	qsort(G,N,sizeof(Gutui),comp);


	//CALCUL MASA DE FRUCT ACUMULUATA
	for (i=0;i<N;i++)
	{
		if (V[G[i].level-1] == 0)
		{
			V[G[i].level-1]=1;
			MASA+=G[i].greutate;
			k++;
		}
		
		else if (V[G[i].level-1] == 1)
		{
			j=G[i].level-1;
			while (V[j] == 1)
			{
				if (j==0)
					break;
				j--;
			}
			if (V[j] == 0)
			{
				V[j]=1;
				MASA+=G[i].greutate;
				k++;
			}
	
		}	

		if (k==max_level)
				break;		
	}
	
	FILE *f2;
	f2=fopen("gutui.out","w");
	fprintf(f2,"%d\n",MASA);
	fclose(f2);
	
	return 0;
}