Pagini recente » Cod sursa (job #1501595) | Cod sursa (job #313219) | Cod sursa (job #2740477) | Cod sursa (job #1114258) | Cod sursa (job #441276)
Cod sursa(job #441276)
#include <stdlib.h>
#include <stdio.h>
typedef struct {
int h;
int g;
int nr;
}gutui;
int compareG(const void *a, const void *b)
{
gutui *aa = (gutui *)a;
gutui *bb = (gutui *)b;
return (bb->g -aa->g);
}
int compareNr(const void *a, const void *b)
{
gutui *aa = (gutui *)a;
gutui *bb = (gutui *)b;
if(aa->nr - bb->nr < 0)
return -1;
return 1;
}
int maxim(gutui *a,int n,int u)
{
int max=0,i;
for(i=0;i<n;i++)
if(a[i].nr>max)
max=a[i].nr;
return max;
}
int main()
{
FILE *fis=fopen("gutui.in","r");
FILE *fis_out=fopen("gutui.out","w");
int n,h_max,u,i,greutate=0,count=0;
fscanf(fis,"%i",&n);
gutui a[n];
fscanf(fis,"%i",&h_max);
fscanf(fis,"%i",&u);
for(i = 0; i < n; i++)
fscanf(fis, "%i %i", &a[i].h,&a[i].g);
qsort(a,n,sizeof(gutui),compareG); //gutui sortate descrescator dupa greutate
for(i=0;i<n;i++)
a[i].nr=1 +(h_max-a[i].h)/u; //nr de gutui pe care le pot culege pana cand nu mai pot lua gutuia resp
int index_max=maxim(a,n,u);
qsort(a,index_max,sizeof(gutui),compareNr); //sortez primele index_max gutui dupa nr
for(i=0;i<n;i++)
printf("%i %i\n",a[i].h,a[i].g);
for(i=0;i<index_max;i++)
if(a[i].h<=h_max)
{
greutate+=a[i].g;
h_max=h_max-u;
count++;
}
//nu am cules nr maxim de gutui
if(count<n)
for(i=index_max;i<n;i++)
if(a[i].h<=h_max)
{ greutate+=a[i].g;
h_max=h_max-u;
}
//printf("%i",greutate);
fprintf(fis_out,"%i",greutate);
//getch();
return 0;
}