Cod sursa(job #1020002)

Utilizator Raducu1992Raducu Raducu1992 Data 1 noiembrie 2013 14:55:45
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 2.98 kb
#include <stdio.h>
#include<stdlib.h>
struct gutui
{
    int greutate,inaltime;
};
struct gutui *v;
void Date(int *N, int *H, int *U)
{
    int i;
    FILE *f = fopen("gutui.in", "rt");
    fscanf(f, "%i%i%i", N,H,U);
    v = (struct gutui*)malloc((*N)*sizeof(struct gutui));
    for(i = 0; i < *N; ++i)
    {
        fscanf(f, "%i", &v[i].inaltime);
        fscanf(f, "%i", &v[i].greutate);
    }
    fclose(f);
}
int compare(const void *x, const void *y){
    return ((struct gutui *)x)->inaltime  - ((struct gutui *)y)->inaltime;
}
int compare2(const void *x, const void *y){
    return ((struct gutui *)x)->greutate  - ((struct gutui *)y)->greutate;
}
void scrieDate(int greutateFinal)
{
    FILE *f = fopen("gutui.out","w");
     fprintf(f,"%d",greutateFinal);
    fclose(f);
}
int min(int a,int b)
{
    if(a < b)
        return a;
    return b;
}
int main()
{
    int i,N,H,U,elem=0,mai_multe=0,stanga,dreapta,h_min,sari_peste=1,rez=0,stop;
    Date(&N,&H,&U);
    struct gutui *b;
    b = (struct gutui*)malloc(N*sizeof(struct gutui));
    qsort( v, N, sizeof(struct gutui),compare); // am sortat dupa h
    // vectorul este sortat crescator dupa h.
    stanga = H-U+1;
    dreapta = H;
    h_min = v[0].inaltime;
    while( dreapta >= h_min )
    {
        for(i = N-sari_peste ; i >= 0; i--) // caut toate h in interval
        {
            if( v[i].inaltime >= stanga && v[i].inaltime <= dreapta)
            {
                b[elem].inaltime = v[i].inaltime;
                b[elem].greutate = v[i].greutate;
                elem++;
                sari_peste++;
            }
        }
        stop = elem - mai_multe;
        if(elem == 0)
        {
            mai_multe++;
        }
        if(elem != 0)
        {
            qsort( b, elem, sizeof(struct gutui),compare2); // sortez b dupa greutate
            if(elem == 1)
            {
                rez += b[elem-1].greutate;
            }
            else if(elem > 1)
            {
                if(mai_multe == 0)
                {
                    rez += b[elem-1].greutate;
                }
                else if(mai_multe > 0)
                {
                    if(elem == mai_multe)
                    {
                        stop = elem-mai_multe;
                    }
                    else if(elem > mai_multe)
                    {
                        stop = elem-mai_multe-1;
                    }
                    else if(elem < mai_multe)
                    {
                        stop = min(elem,mai_multe)-1;
                    }
                    for(i = elem-1; i >= stop; --i)
                    {
                        rez += b[i].greutate;
                    }
                }

            }
        }
        free(b);
        b = (struct gutui*)malloc(N*sizeof(struct gutui));
        elem = 0;
        stanga -= U;
        dreapta -= U;
    }
  //  printf("%d",rez);
    scrieDate(rez);

 return 0;
}