Cod sursa(job #432454)

Utilizator wildchildWild Child wildchild Data 2 aprilie 2010 13:12:58
Problema Gutui Scor 20
Compilator c Status done
Runda teme_upb Marime 3.26 kb
#include <stdio.h>
#include <stdlib.h>

/* Variabile globale */
//long ** g;                // gutuile sunt inregistrate intr-un vector de vectori in functie de nivelul (H-Hgutuie)/U la care se gaseste gutuia
long * g;                   // vectorul de gutui (greutati)
long * h;                   // vectorul de inaltimi per gutuie
long N;                     // nr de gutui
long H;                     // inaltimea maxima la care ajunge Gigel
long U;                     // cu cat se ridica ramurile dupa culegerea unei gutui 
long gMax;                  // greutatea maxima culeasa

/* Declaratii functii */
void citire();				// citirea fisierului de intrare
void afisare();				// afisarea rezultatelor
void rezolvare();			// rezolvaea problemei

/* Main */
int main(int argc, char *argv[]) {

	citire();				// citire date de intrare
	rezolvare();			// rezolvare problema
	afisare();   			// afisare rezultate
	
	return 0;
}

/* Definitii functii */

/* citirea fisierului de intrare */
void citire() {
    FILE * in;				// fisier de intrare
    long i,gg,hg;  			// auxiliari
	
    // deschidem fisier de intrare
	in = fopen("gutui.in","rt");
	
    fscanf(in, "%ld%ld%ld", &N, &H, &U);  // citire N, H, U
    // alocam memorie pentru vectorul de gutui si cel de inaltimi
    g = malloc (N * sizeof(long));
    h = malloc (N * sizeof(long));

    for (i=0;i<N;i++){
        // citire gutui
        fscanf(in, "%ld %ld", &hg, &gg);
        g[i] = gg;
        h[i] = hg;             
    }
	
    gMax = 0;               // initializare gMax
	
	// inchidem fisier de intrare
    fclose(in);
}

/* afisarea rezultatelor */
void afisare() {
    FILE * out; 			// fisier de iesire
	
	// deschidem fisier de iesire
    out = fopen("gutui.out","wt");
	
    fprintf(out,"%ld", gMax);
	
	// inchidem fisier de iesire
    fclose(out);
}

/* Rezolvarea problemei */
void rezolvare() {
     long * picked;             // picked[i] = cate gutui au fost culese de pe niveluri <= i, maximul acceptat fiind i
     long k;                    // numar de niveluri ale pomului
     long i,j,jMax,kj;          // auxiliari
     int done;                  // semnaleaza ca nu mai sunt gutui de cules (greutatea maxima ce poate fi culeasa e 0)
     // calcul k
     k = 0;
     for (i = 0; i<N; i++)
         if ((H-h[i])/U + 1 > k)
            k = (H-h[i])/U + 1;
     
     // alocam memorie si initializam picked
     picked = malloc ((k+1) * sizeof(long));
     for (i = 0; i<k+1; i++)
         picked[i] = 0;
         
     i=0;
     done = 0;
     while (i<N && picked[k] < k && !done){
         jMax = 0;
         for (j = 0; j < N; j++){
             // cautam cea mai grea gutuie pe care o putem culege
             // conditia e ca picked[kj] < kj, unde kj = nivelul gutuii j, adica (H-h[j])/U + 1
             kj = (H - h[j])/U + 1;
             if (g[j] > g[jMax] && picked[kj] < kj)
                jMax = j;
         }
         // actualizam gMax, picked, i si done
         if (g[jMax] <= 0)
            done = 1;
         gMax += g[jMax];
         g[jMax] = 0;
         for (j = (H-h[jMax])/U + 1; j<k+1; j++)
             picked[j] ++;    
         i++;    
     }
     
     free (g);
     free (h);
     free (picked);
          
}