Cod sursa(job #441629)

Utilizator MikhinjaCatalina Mihai Vlad Mikhinja Data 12 aprilie 2010 23:55:29
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 1.31 kb
/*
Catalina Mihai Vlad
334CB
Problema - Gutui
Complexitate O(N^2)
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct {
int g,h;
} gutuie;
int comp(const void *a,const void *b){
 gutuie *x, *y;
x=( gutuie*)a;
y=( gutuie*)b;
return (y->h - x->h);
}
int main(void){
int N,H,U,G=0,i,j,aux,aux2;
FILE *f;
f=fopen("gutui.in","r");
fscanf(f,"%i%i%i",&N,&H,&U);
gutuie gutui[N];
int indici[N];
for(i=0;i<N;i++){
	fscanf(f,"%i%i",&(gutui[i].h),&(gutui[i].g));
}
fclose(f);
printf("%3i\n",comp(gutui,gutui+1));

qsort(gutui,N,sizeof(gutuie),comp);

for(i=0;i<N;i++){
	printf("gutui[%3i] %3i %3i\n",i,gutui[i].g,gutui[i].h);
}

aux=0;//aux va contoriza cate gutui au fost culese
for(i=0;i<N;i++)
	if( gutui[i].h + aux * U <= H ){
		
		G   += gutui[i].g;//adun
		
		indici[aux++]=i;//culeg gutuia curenta
		
		
	}
	else {aux2=aux;
		indici[aux]=i;
		
		for(j=0;j<aux;j++){
			
			if(gutui[indici[j]].g < gutui[indici[aux2]].g)
				aux2=j;//aflu minimul dintre cele culese si curenta
		}
		if(aux2!=aux){//daca minimul este alta decat gutuia curenta
			
			G += gutui[indici[i]].g - gutui[indici[aux2]].g;//adun diferenta
			
			indici[aux2]=i;//schimb fosta gutuie culeasa cu actuala
		}
	}

f=fopen("gutui.out","w");
fprintf(f,"%i",G);
fclose(f);
return 0;
}