Cod sursa(job #439954)

Utilizator adytzu2007Adrian Bacircea adytzu2007 Data 11 aprilie 2010 20:57:00
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 3.01 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct nod {
    struct nod *next;
    long int val;
} nod;

typedef struct colectie {
    struct nod **lista;
    long int *cheie;
    long int n;
    long int cap;
} colectie;

void initC(struct colectie *c)
{
    c->cheie = (long int*)malloc(sizeof(long int));
    c->lista = (struct nod**)malloc(sizeof(struct nod*));
    c->n = 0;
    c->cap = 1;
}

void initL(struct colectie *c, long int i)
{
    c->lista[i] = NULL;
}

void addL(struct colectie *c, long int i, long int elem)
{
    struct nod *element,*t,*prevt;
    int adaugat = 0;
    element = (struct nod*)malloc(sizeof(nod));
    element->next = NULL;
    element->val = elem;
    t = c->lista[i];
    prevt = NULL;
    while (t!=NULL && !adaugat)
    {
        if (t->val < element->val) {
            if (prevt == NULL) {
                c->lista[i]=element;
                element->next = t;
            }
            else {
                prevt->next = element;
                element->next = t;
            }
            adaugat = 1;
        }
        else {
            prevt = t;
            t = t->next;
        }
    }
    if (!adaugat) {
        if (prevt == NULL)
            c->lista[i] = element;
        else
            prevt->next = element;
    }
}

void addC(struct colectie *c, long int cheie, long int val)
{
    int nou = 1,i;
    for (i=0;i<c->n && nou;i++)
        if (c->cheie[i] == cheie) {
            nou = 0;
            addL(c, i, val);
        }
    if (nou) {
        c->n++;
        if (c->n > c->cap) {
            c->cap++;
            c->lista = (struct nod**)realloc(c->lista, sizeof(struct nod*)*c->cap);
            c->cheie = (long int*)realloc(c->cheie, sizeof(long int)*c->cap);
        }
        initL(c,c->n-1);
        addL(c,c->n-1,val);
        c->cheie[c->n-1] = cheie;
    }
}

int main()
{
    FILE *f = fopen("gutui.in", "r");
    FILE *g = fopen("gutui.out","w");
    long int i,j,n,hmax,u,x,y,nivel,nivmax=0;
    long int suma = 0;
    struct colectie col;
    struct nod *t;
    initC(&col);
    fscanf(f,"%ld %ld %ld",&n,&hmax,&u);
    for (i=1;i<=n;i++) {
        fscanf(f,"%ld %ld",&x,&y);
        nivel = (hmax-x)/u + 1;
        if (hmax%u == 0) nivel--;
        if (nivel > nivmax) nivmax = nivel;
        addC(&col, nivel, y);
    }
    for (i=0;i<col.n;i++) {
        t = col.lista[i];
        j = 0;
        while (t != NULL && j<col.cheie[i]) {
            addC(&col,-1,t->val);
            t = t->next;
            j++;
        }
    }
    /*for (i=0;i<col.n;i++) {
        t = col.lista[i];
        printf("Nivel %d: ",col.cheie[i]);
        while (t!=NULL) {
            printf("%d ",t->val);
            t = t->next;
        }
        printf("\n");
    }*/
    suma = 0;
    i=col.n-1;
    j=0;
    t=col.lista[i];
    while (t!=NULL && j<nivmax) {
        suma+=t->val;
        t = t->next;
    }
    fprintf(g,"%ld",suma);
    fclose(g);
    fclose(f);
    return 0;
}