Cod sursa(job #435668)

Utilizator adrian.bosilcaBosilca Adrian adrian.bosilca Data 7 aprilie 2010 19:05:39
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 1.75 kb
/*
 * File:   Problema2.c
 * Author: Bosilca Adrian 325CC
 *
 */

#include <stdio.h>
#include <stdlib.h>

int u;

typedef struct gutuie{
    int h;
    int g;
}gutuie;

void afisare(gutuie v[], int n) {
    int i;
    for (i = 0 ; i < n ; i++) {
        printf("%d %d %d\n", v[i].g, v[i].h, i*10);
    }
    printf("\n");
}

int comp(const void* a, const void* b) {
    gutuie *c = (gutuie*)a;
    gutuie *d = (gutuie*)b;
    if (c->g == d->g)
        return (d->h - c->h);
    return ( d->g - c->g );
}

int main() {
    FILE* f = fopen("gutui.in", "r");
    int n, h, i, j, dif = 0, k = 0, s = 0;
    gutuie v[100000], aux;
    //int best[100000];

    fscanf(f, "%d %d %d", &n, &h, &u);            //citirea datelor de intrare

    for (i = 0 ; i < n ; i++) {
        fscanf(f, "%d %d", &v[i].h, &v[i].g);
    }
    fclose(f);

    qsort(v, n, sizeof(gutuie), comp);

     afisare(v, n);

    for (i = 0 ; i < n, k < n; k++) {
        dif = i*u;
       // printf("v[%d].h = %d\n", i, v[i].h);
        if (v[i].h+dif+u <= h) {
            aux = v[i];
            dif = dif + u;
           // printf("aux =%d dif =%d\n", aux.h, dif);
            for (j = i ; aux.h+dif <= h ; j++) {
                v[j] = v[j+1];
                dif = dif + u;
            }
            v[j] = aux;
            afisare(v, n);
        }
        dif = i*u;
        if (v[i].h+dif+u > h)
            i++;
    }

    afisare(v, n);

    /*for (i = 0 ; i <n ; i++) {
        dif = i*u;
        if (v[i].h + dif <= h)
            s = s + v[i].g;
        else
            break;
    }*/

    dif = 0;
    for (i = 0 ; i < n; i++) {
        if (v[i].h+dif <= h) {
            s += v[i].g;
            dif += u;
        }
    }

    f = fopen("gutui.out", "w");
    fprintf(f, "%d", s);
    fclose(f);

    return 0;
}