Cod sursa(job #440471)

Utilizator DetudaArthur Koestler Detuda Data 12 aprilie 2010 02:06:37
Problema Gutui Scor 30
Compilator c Status done
Runda teme_upb Marime 3.44 kb
#include<stdio.h>
#include<malloc.h>

typedef struct {
    int inaltime;
    int greutate;
    } gutuie;

//interschimba 2 elemente din vectorul de gutui
void swap(gutuie *a, gutuie *b) {
    gutuie aux;
    aux=*a;
    *a=*b;
    *b=aux;
}

//auxiliar pentru functia de sortare quicksort
int choose_pivot(int i, int j) {
    return ((i+j)/2);
}

//sorteaza descrescator in functie de greutate in vectorul de gutui
void quicksort(gutuie *g, int m, int n) {   
    int key,i,j,k;
    if (m<n)
        {
            k=choose_pivot(m,n);
            swap(&g[m],&g[k]);
            key=g[m].greutate;
            i=m+1;
            j=n;
            while (i<=j)
                {
                while ((i<=n)&&(g[i].greutate>=key))
                    i++;
                while ((j>=m) &&(g[j].greutate<key))
                    j--;
                if (i<j)
                    swap(&g[i],&g[j]);
                }
            swap(&g[m],&g[j]);
            quicksort(g,m,j-1);
            quicksort(g,j+1,n);
        }
    }
   
int main() {
    //DECLARARI VARIABILE
    int n,h,u,i,gt=0,cnt=-1,j,localizare;
    FILE *in=fopen("gutui.in","r");
    FILE *out=fopen("gutui.out","w");
   
    fscanf(in,"%d",&n);
   
    //ALOCARI DE MEMORIE
    gutuie *g=(gutuie*)malloc(n*sizeof(gutuie));
    int *ord=(int*)malloc(n*sizeof(int));
    int *maxime=(int*)malloc(n*sizeof(int));
    int *nrg=(int*)malloc(n*sizeof(int));
   
    //CITIRE DIN FISIER SI COMPLETARE CAMPURI GUTUI   
    fscanf(in,"%d%d",&h,&u);
    for (i=0;i<n;i++)
        fscanf(in,"%d%d",&g[i].inaltime,&g[i].greutate);
    /*
    for (i=0;i<n;i++)
        printf("%d %d\n",g[i].inaltime,g[i].greutate);
    printf("\n");   
    */
    quicksort(g,0,n-1);
    /*
    for (i=0;i<n;i++)
        printf("%d %d\n",g[i].inaltime,g[i].greutate);
    printf("\n");
    */
    //formez vectorul ord   
    for (i=0;i<n;i++) {
        if (g[i].inaltime>h)
            ord[i]=-1;
        else
            ord[i]=(h-g[i].inaltime)/u;
    }
       
    for (i=0;i<n;i++)
        if (ord[i]!=-1) {
            if (i==0) {
                maxime[++cnt]=ord[i];
                nrg[cnt]=ord[i]+1;
                gt+=g[i].greutate;
                nrg[cnt]--;
            }
            else {
                if (ord[i]>maxime[cnt]) {
                    maxime[++cnt]=ord[i];
                    nrg[cnt]=maxime[cnt]-maxime[cnt-1];
                    gt+=g[i].greutate;
                    nrg[cnt]--;
                    }
                else {
                    localizare=-1;
                    for (j=0;j<=cnt;j++) {
                        if (j==0 && ord[i]>=0 && ord[i]<=maxime[j])
                            localizare=0;
                        if (j!=0 && ord[i]>maxime[j-1] && ord[i]<=maxime[j])
                            localizare=j;
                        if (localizare!=-1)
                            break;
                        }
                    while (localizare>=0) {
                        if (nrg[localizare]>0) {
                            gt+=g[i].greutate;
                            nrg[localizare]--;
                            break;
                        }
                        else
                            localizare--;
                    }
                               
                    }
                }
            }
       
    fprintf(out,"%d\n",gt);       
   
return 0;
}