Cod sursa(job #441111)

Utilizator andra_serbanSerban Andra-Elena andra_serban Data 12 aprilie 2010 19:23:04
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 3.95 kb
/********************************/
/*  Nume:  Serban Andra - Elena */
/*  Grupa: 325CC                */
/********************************/


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

int n;
int N;
int H;
int U;
int inaltime[100003];
int greutate[100003];
int count[100003];

/* Functie pentru scrierea in fisier a unei valori intregi */
void write(int x) {

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

    fprintf(g, "%d", x);

}

/* Functia de partitie pentru algoritmul de sortare implementat prin algoritmul quicksort */
int partition(int left, int right) {

    int pivot, i, j, aux;

    pivot = greutate[left];
    i = left;
    j = right + 1;

    while (1) {
        do
            i++; 
        while (greutate[i] <= pivot && i <= right);
        do
            j--;
        while (greutate[j] > pivot);
        if (i >= j)
            break;
        /* Se sorteaza dupa greutate si in acelasi timp se interschimba si inaltimea, pentru a pastra corelatia greutate-inaltime asociata unei gutui */
        aux = greutate[i];
        greutate[i] = greutate[j];
        greutate[j] = aux;
        aux = inaltime[i];
        inaltime[i] = inaltime[j];
        inaltime[j] = aux;
    }

    aux = greutate[left];
    greutate[left] = greutate[j];
    greutate[j] = aux;
    aux = inaltime[left];
    inaltime[left] = inaltime[j];
    inaltime[j] = aux;

    return j;

}

/* Sortare, crescatoare, folosind algoritmul de quicksort */
void sort(int left, int right) {

    int j;

    if (left < right) {
        j = partition(left, right);
        sort(left, j - 1);
        sort(j + 1, right);
    }

}

/* Functia "gutui" calculeaza greutatea maxima ce poate fi culeasa de Gigel */
void gutui() {

    int i, j, nivel, ok;
    int suma = 0;
    int max = 0;

    /*   Pasul maxim la care poate fi luata o gutuie, adica numarul de gutui pe care le putem lua inaintea celei curente astfel incat sa o mai putem lua si si pe aceasta
     * se poate calcula cu relatia (H - h) / U, unde H si U au semnificatia din enunt, iar h este inaltimea la care se afla gutuia curenta.
     *   Vom calcula cel mai mare astfel de pas (notat: "max") si vom crea un vector, count care are initial numere d ela 1 la max. 
     */
    for (i = 1; i <= N; i++)
        if ((H - inaltime[i]) / U + 1 > max)
            max = (H - inaltime[i]) / U + 1;

    for (i = 1; i <= max; i++)
        count[i] = i;

    /* Sortam informatiile despre gutui, crescator,  in functie de greutate */
    sort(1, N);

    /*   Deoarece trebuie sa luam cea mai mare greutate posibila, vom lua din pom gutuile in ordinea greutatii lor si le marcam cu pasul maxim la care pot fi luate,
     * schimbam elementul din vectorul count de pe pozitia pasului, in 0 si adunam greutatea gutuii la suma totala.
     *   Daca pasul maxim la care poate fi luata o gutuie(notat: "nivel") a fost deja folosit ( daca count[nivel] = 0 ), atunci cautam in vectorul count cea mai mare
     * valoare diferita de 0, mai mica decat "nivel", o marcam cu 0 si adunam greutatea gutuii la suma totala.
     *   Altfel, daca nu gasim in vectorul count nici un element diferit de 0, mai mic, sau egal cu pasul maxim la care poate fi luata gutuia, inseamna ca nu o mai putem lua
     * si trecem la urmatoarea gutuie.
     */
    for (i = N; i >= 1; i--) {
        nivel = (H - inaltime[i]) / U + 1;
        ok = 0;
        for (j = nivel; j >= 1; j = j - 1) {
            if (ok != 1)
                if (count[j] != 0) {
                    ok = 1;
                    count[j] = 0;
                    suma = suma + greutate[i];
                }
        }
    }

    write(suma);

}

int main() {

    FILE *f = fopen("gutui.in", "r");
    int i;

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

    for (i = 1; i <= N; i++) {
        fscanf(f, "%d", &inaltime[i]);
        fscanf(f, "%d", &greutate[i]);
    }

    gutui();

    return 0;

}