Cod sursa(job #441128)

Utilizator GeorgianneGircu Georgiana Georgianne Data 12 aprilie 2010 19:29:50
Problema Gutui Scor 30
Compilator c Status done
Runda teme_upb Marime 1.55 kb
#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;
    return (aa->nr -bb->nr);
}
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,j,aux=0,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<index_max;i++)
     if(a[i].h<=h_max)
      {
         greutate+=a[i].g;
         h_max=h_max-u;
         count++;
        }
     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; 
}