Pagini recente » Cod sursa (job #1630633) | Cod sursa (job #1565185) | Cod sursa (job #3182856) | Cod sursa (job #1233656) | Cod sursa (job #441629)
Cod sursa(job #441629)
/*
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;
}