Cod sursa(job #436100)

Utilizator adela.balasaAdela Balasa adela.balasa Data 8 aprilie 2010 02:16:51
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 1.65 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int h;  //inaltimea
    int g;  //greutatea
    int cules;
}gutuie;

int N,H,U;
float *best;
int t;
int sum=0;

int main() {
    int i;

    FILE* in=fopen("gutui.in","r");
    FILE* out=fopen("gutui.out","w");

    fscanf(in,"%d%d%d",&N,&H,&U);

    gutuie *G = (gutuie*)calloc(N,sizeof(gutuie));
    best = (float*)calloc(N,sizeof(float));

    for (i=0;i<N;i++) {
        fscanf(in,"%d%d",&G[i].h,&G[i].g);
        G[i].cules=0;
    }

    //ordonare descrescatoare dupa h
    int ok;
    gutuie aux;
    do {
        ok=0;
        for(i = 0; i < N-1; i++)
            if( G[i].h < G[i+1].h ) {
                ok=1;
                aux = G[i];
                G[i]=G[i+1];
                G[i+1]=aux;
            }
    } while(ok);

    for (i=0;i<N;i++)
        printf("%d %d\n",G[i].h, G[i].g);



    int more=1;
    t=0;
    while (more) {
        more=0;
        for (i=0;i<N;i++)
            best[i]=0;
        for(i=0;i<N;i++)
            if (G[i].h+t*U<=H && !G[i].cules) {
                more=1;
                best[i]=(float)G[i].g / (H-(G[i].h+t*U));
            }
        if (more) {
            float max=0;int maxi=-1;
            for (i=0;i<N;i++)
                if (best[i]>max) {
                    max=best[i];
                    maxi=i;
                }
            if(maxi!=-1) {
                printf("%d ",maxi);
                sum+=G[maxi].g;
                G[maxi].cules=1;
                t++;
            }
        }
    }

    fprintf(out,"%d",sum);


    free(G);
    fclose(in);
    fclose(out);

}