Pagini recente » Cod sursa (job #1459329) | Cod sursa (job #1713393) | Cod sursa (job #1974801) | Cod sursa (job #2714417) | Cod sursa (job #438954)
Cod sursa(job #438954)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
typedef struct{
unsigned int h; //inaltimea crengii pe care se afla gutuia
unsigned int g; //greutatea gutuii
unsigned int level;
} gutuie;
int compara(void* a,void* b)
{
unsigned int val_a,val_b,vala,valb;
val_a=(*((gutuie *)a)).g;
val_b=(*((gutuie *)b)).g;
vala=(*((gutuie *)a)).level;
valb=(*((gutuie *)b)).level;
if(vala<valb)
return 1;
else
if(vala>valb)
return -1;
else
{
if(val_a<val_b)
return 1;
else
if(val_a>val_b)
return -1;
else
return 0;
}
}
int main()
{
//deschidere fisier de intrare, respectiv fisier de iesire
FILE *in,*out;
in=fopen("gutui.in","r");
out=fopen("gutui.out","w");
//citim numarul de gutui, inaltimea maxima si cu cat se ridica crengile
int N,H,U;
fscanf(in,"%d%d%d",&N,&H,&U);
gutuie *date,*sol;
date=(gutuie*) calloc(N,sizeof(gutuie));
sol=(gutuie*) calloc(N,sizeof(gutuie));
int i,*vmin;
unsigned int nr_max_gutui;
vmin=(int*)calloc (N,sizeof(int));
for(i=0;i<N;i++)
fscanf(in,"%u%u",&date[i].h,&date[i].g);
for (i=0;i<N;i++)
date[i].level=(H-date[i].h)/U+1;
qsort(date,N,sizeof(gutuie),(__compar_fn_t)&compara);
// for(i=0;i<N;i++)
// printf("%u %u\n",date[i].h,date[i].g);
unsigned int minim=date[0].h;
for(i=1;i<N;i++)
if(date[i].h<minim)
minim=date[i].h;
//printf("%u\n",minim);
nr_max_gutui=(H-minim)/U + 1; //cate gutui ar putea fi maxim culese a.i. sa se respecte conditiile
int culese=0;
long int suma=0;
int j,min,k;
for (i=0;i<N;i++)
{ if (culese<nr_max_gutui && date[i].level>culese)
{sol[i]=date[i]; culese++;
if(min>sol[i].g) {min=sol[i].g; k=i;vmin[j++]=min;}}
else
{if (date[i].g>min) sol[k]=date[i];min=vmin[j--];}
}
for (i=0;i<nr_max_gutui;i++)
suma=suma+ date[i].g;
fprintf(out,"%ld\n",suma);
free(date);
fclose(in);
fclose(out);
return 0;
}