Cod sursa(job #441065)

Utilizator GeorgianneGircu Georgiana Georgianne Data 12 aprilie 2010 19:00:50
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 1.89 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("gutui3.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); 
  
  for(i=0;i<index_max;i++)
    qsort(a,index_max,sizeof(gutui),compareNr);  //sortez primele index_max gutui dupa nr
  /*  for(i=0;i<index_max;i++)
       printf("%i - %i- %i\n",a[i].h,a[i].g,a[i].nr);
    for(i=0;i<n;i++)
     printf("%i - %i - %i\n",a[i].h,a[i].g,a[i].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)   //mai am gutui de cules
    {
      for(i=index_max;i<n;i++)
        if(a[i].h<=h_max)
             { greutate+=a[i].g;
               h_max=h_max-u;
               }
                    
     }
  //    printf("Greutate max: %i\n",greutate);
   // for(i=0;i<n;i++)
     //printf("%i - %i \n",a[i].h,a[i].g);
  fprintf(fis_out,"%i",greutate);
// getch();
   return 0; 
}