Cod sursa(job #463117)

Utilizator simona.poilincaSimona Poilinca simona.poilinca Data 14 iunie 2010 16:56:15
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 1.44 kb
//Georgian Oana Raluca Grupa 321CA
#include<stdio.h>
#include<stdlib.h>

typedef struct{
	int greutate;
	int inaltime;
}Gutuie;

int compare(const void* elem1, const void* elem2)
{
   return ((Gutuie*)elem2)->greutate - ((Gutuie*)elem1)->greutate;
}





int main()
{
//initializari variabile
Gutuie *gut;
int N,u,H;
int i,j;
int max=0;
int hi,g;
int *cules;
FILE *fin,*fout;
//deschidere fisier
fin=fopen("gutui.in","r");
fout=fopen("gutui.out","w+");

fscanf(fin,"%d",&N);
fscanf(fin,"%d",&H);
fscanf(fin,"%d",&u);
//alocare memorie
gut=(Gutuie*)calloc(N,sizeof(Gutuie));

//citire date din fisier
for(i = 0; i < N; i++)
	{	
		fscanf(fin,"%d",&gut[i].inaltime);
		fscanf(fin,"%d",&gut[i].greutate);
	}

//sortare gutui dupa greutate
qsort((void *)gut,N,sizeof(Gutuie),compare);

//cautam numarul maxim de gutui care ar putea fi culese
for(i = 0; i < N; i++)
	{
		hi=(H-gut[i].inaltime)/u;
		if(max< hi)
			max=hi;
		}
j=0;
//alocare memorie vector pentru gutuile culese		
cules=(int *)calloc((max+1),sizeof(int));

for(i = 0; i < N; i++)
	{
		hi=(H-gut[i].inaltime)/u;
		
		//contorizez gutuile
		while(cules[hi]!=0 && hi>=0)
				hi--;
		if(hi < 0)
			continue;
			
		if(cules[hi]==0)
			cules[hi]=gut[i].greutate;
				j++;
//ma opresc daca am cules numarul maxim de gutui ce puteau fi culese
		if(j == max+1)
			break;
	}
g=0;
//greutatea gutuilor culese
for(i=0;i<=max;i++)
	g+=cules[i];
fprintf(fout,"%d",g);
//eliberare memorie			
free(gut);
free(cules);
return 0;

}