Cod sursa(job #442123)

Utilizator GeorgianneGircu Georgiana Georgianne Data 13 aprilie 2010 21:41:45
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 1.9 kb
#include <stdlib.h>
#include <stdio.h>

typedef struct {
  int h;
  int g;
  int level;
 }gutui;

int compareG(const void *a, const void *b) 
{
    gutui *aa = (gutui *)a;
    gutui *bb = (gutui *)b;
    return ((*bb).g -(*aa).g);
}
int main()
{
    FILE *fis=fopen("gutui.in","r");
    FILE *fis_out=fopen("gutui.out","w");
    int n,h_max,u,i,max=0,greutate=0,j;
    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].level=1+(h_max-a[i].h)/u; //levelul reprezinta pt fiecare gutuie numarul maxim de gutui pe care il pot culege
      if (a[i].level>max)          //pana cand gutuia nu o sa mai poata fi accesata
         max=a[i].level;
      }
 int test[max+1];
     for(i=0;i<=max;i++)
           test[i]=0; 
     for(i=0;i<n;i++)
     {
       int ok=0;
      if(test[a[i].level]==0 ) //nu am mai luat nicio gutuie de pe level->gutuia curenta are greutatea maxima de pe level
            {
                       test[a[i].level]=1; //marchez faptul ca am luat o gutuie de pe levelul curent
                       {
                         greutate+=a[i].g;
                         printf("Am pus greutatea :%i\n",a[i].g);
                        // ok=1;
                         
                        }
            } 
           else 
              for(j=a[i].level;j>0;j--) 
                if(test[j]==0 && ok==0)   //mai puteam lua o gutuie de pe o ramura de mai de sus ?
            {
                        test[j]=1;
                        greutate+=a[i].g;
                        printf("Am pus greutatea :%i\n",a[i].g);
                        ok=1;
            }              
      }
  fprintf(fis_out,"%i",greutate);
   return 0; 
}