Cod sursa(job #427091)

Utilizator Cristina_89Cristina Savin Cristina_89 Data 27 martie 2010 15:10:05
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 1.73 kb
#include <stdio.h>

int *hh,*gg,*pus;
int n,h,u,crt;
#define CRESC 10

//functie de sortare dupa inaltime=> tb inlocuita ca sa fie in nlogn
//tb un quicksort
void sort()
{
     int i,j,t;
     for(i=0;i<n-1;i++)
        for (j=i+1;j<n;j++)
            if (hh[i]>hh[j]) {t=hh[i];hh[i]=hh[j];hh[j]=t;
                              t=gg[i];gg[i]=gg[j];gg[j]=t; }  
     
}

//cauta maximul dupa pasi
int maxim(int pasi)
{
    int ok=0,max=-1,poz=-1,i;
    for (i=crt;i>=0;i--)
        //daca se poate lua
        if (!pus[i] && (hh[i]+u*pasi)<=h)
        {  
           ok=1;
           //am ajuns la primul care se poate lua dupa inca 2 pasi
           //pana aici i-am parcurs pe cei care se pot lua doar dupa 1 pas
           if (hh[i]+u*(pasi+1)<=h) break;
           else 
           //caut maximul intre cei care se pot lua doar dupa 1 pas
                if (gg[i]>max) {max=gg[i];poz=i;}
        }
    //nu am gasit nici unul    
    if (!ok) return -1;
    if (poz==-1) poz=i;
    crt=i;
    pus[poz]=1;return gg[poz];    
}
    
    
int main()
{
    int i;
    FILE *fis=fopen("gutui.in","r");
    fscanf(fis,"%d%d%d",&n,&h,&u);

    hh=(int*)malloc(n*sizeof(int));
    gg=(int*)malloc(n*sizeof(int));
    pus=(int*)malloc(n*sizeof(int));
    
    for(i=0;i<n;i++)
       {fscanf(fis,"%d%d",&hh[i],&gg[i]);pus[i]=0;}
    fclose(fis);
    
    sort();
    
    int pasi=0;
    int gr=0;
    int tmp;
    crt=n-1;
    //crt e ultima pozitie la care am ajuns
    while(1)
    {
         tmp=maxim(pasi);
         if (tmp<0) break;
         gr+=tmp;
         pasi++;
    }            
    FILE *fis1=fopen("gutui.out","w");
    fprintf(fis1,"%d\n",gr);
    fclose(fis1);
    
    return 0;   
}