Cod sursa(job #432599)

Utilizator wildchildWild Child wildchild Data 2 aprilie 2010 15:50:56
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 3.61 kb
#include <stdio.h>
#include <stdlib.h>

/* Variabile globale */
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;  	      		// auxiliar
	
    // 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", &h[i], &g[i]);             
    }
	
    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)
     long maxDone;              // nivelul pana la care a fost cules numarul maxim de gutui
     
     // calcul k
     k = 0;
     for (i = 0; i<N; i++)
         if ((H-h[i])/U + 1 > k && H-h[i]>=0)
            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;
     maxDone = 0;
     while (i < N && maxDone < k && !done){
         i++;
         jMax = 0;
         for (j = 0; j < N; j++){
             // cautam cea mai grea gutuie pe care o putem culege
             // conditia e ca maxDone < kj, unde kj = nivelul gutuii j, adica (H-h[j])/U + 1, iar maxDone e nivelul maxim sub care(inclusiv el) nu mai putem culege
             if (H-h[j] >=0){
                 kj = (H - h[j])/U + 1;
                 if (kj <= maxDone)
                    g[j] = 0;
                 if (g[j] > g[jMax])
                    jMax = j;
             }
             else{
                 g[j] = 0;
             }     
         }/*
         // actualizam gMax, picked, i si done
         if (g[jMax] <= 0)
            done = 1;
         else{   
            gMax += g[jMax];
            g[jMax] = 0;
            for (j = (H-h[jMax])/U + 1; j<k+1; j++){
                picked[j] ++;
                if (picked[j]==j && j>maxDone){
                   maxDone = j;
                }
            }
         }   */  
     }
     
     free (g);
     free (h);
     free (picked);          
}