Cod sursa(job #439659)

Utilizator anaitsircVoicu Cristiana anaitsirc Data 11 aprilie 2010 18:09:23
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 1.37 kb
//Voicu Cristiana 325CC

#include <stdlib.h>
#include <stdio.h>


typedef struct{
	int h;
	int g;
}gutuie;


int compare(const void *a,const void *b){
	gutuie * first=(gutuie *) a;
	gutuie * second=(gutuie *) b;
	return (second->g - first->g);
}
int main(){
gutuie sir[100000];
int i;
FILE *fp=fopen("gutui.in","r");
FILE *fp1=fopen("gutui.out","w");
char s[80];
fgets(s,80,fp);

char *sep=" ";
int N=atoi(strtok (s,sep));

int H=atoi(strtok (0,sep));

int U=atoi(strtok (0,sep));

int n=0;
int * a= (int*) calloc (H/U+2, sizeof(int) );
int niv;
int max=0;
int nr1=0;
int nr=0;
int g=0;	//numar greutatea
while ( fgets(s,80,fp) != NULL ){
	sir[n].h=atoi(strtok (s,sep));
	sir[n].g=atoi(strtok (0,sep));
	niv=(H-sir[n].h)/U+1;
	a[niv]++; //retin in vectorul a nivelul initial fiecarei gutui
	n++;
}//end while

fclose (fp);

qsort(sir,N,sizeof(gutuie),compare); 	//sortez vectorul de gutui dupa greutate



for(i=1;i<=H/U+1;i++){
	nr=nr+a[i];
	if (nr>i) nr=i;		//in nr voi avea cate gutui pot culege, iar daca la un pas sunt prea multe le limitez
	a[i]=0;		//refac vectorul de 0-uri
}



for( i=0; i<N;i++){
	if (nr1==nr) break;
	n=(H-sir[i].h)/U+1;
	 
	while ((a[n]!=0) && (n>0))
		n--;
	if (n>max) max=n;
	if (n>0) {
		a[n]=sir[i].g;  //pun in vectorul a greutatile gutuii respective
		nr1++;
	}		
}

for (i=1; i<=max; i++){
	
	if (a[i]!=0)
		g=g+a[i];
	
	
}
fprintf(fp1,"%d",g);
fclose(fp1);
}