Cod sursa(job #440902)

Utilizator GeorgianneGircu Georgiana Georgianne Data 12 aprilie 2010 17:29:56
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 1.96 kb
#include <stdlib.h>
#include <stdio.h>

typedef struct {
  int h;
  int g;
}gutui;
int compareG(const void *a, const void *b) 
{
    gutui *aa = (gutui *)a;
    gutui *bb = (gutui *)b;
    return (bb->g -aa->g);
}

int maxim(gutui *a,int n,int u)  
{ 
  int max=0,i;
  for(i=0;i<n;i++)
         if(a[i].h>max)
              max=a[i].h;
return max;
}

/*int retrieve(int test[],int level,int h_max,int u,gutui *a)
{  
     if(test[level]==0)  
            {
                       test[level]=1;
                       return 1;
            }  
            if(test[level]>0) 
              for(level;level>0;level--) 
              if(test[level]==0) //daca mai pot lua gutui
            {
                       test[level]=1;
                       return 1;
            } 
             
   return 0;
}*/
int retrieve(int test[],int level,int h_max,int u,gutui *a,int index_max)
{  
   
   int i,ok=0;
   if(level<=index_max)
         return 1;
    return 0;      
}
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;
    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
   int test[h_max/u+1];
     for(i=0;i<=h_max/u;i++)
           test[i]=0;                  
     for(i=0;i<n;i++)
            a[i].h=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++)
   if(retrieve(test,a[i].h,h_max,u,a,index_max)==1)
              greutate+=a[i].g;
      // printf("Greutate max: %i\n",greutate);
   // for(i=0;i<n;i++)
    //   printf("%i - %i gut max : %i\n",a[i].h,a[i].g,test[i ]);
  fprintf(fis_out,"%i",greutate);
 //getch();
   return 0; 
}