Cod sursa(job #432645)

Utilizator wildchildWild Child wildchild Data 2 aprilie 2010 16:21:06
Problema Gutui Scor 80
Compilator c Status done
Runda teme_upb Marime 4.29 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
void quick(long left,long right);        // quicksort
long pos(long left,long right);          // determinarea pivotului la quicksort

/* 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;
     
     // sortam vectorii prin metoda quicksort in functie de greutatea gutuilor  
     quick(0,N);
       
     j=0;
     done = 0;
     maxDone = 0;
     while (j < N && maxDone < k){
         // la pozitia curenta j avem cea mai grea gutuie neculeasa, trebuie sa verificam daca avem voie sa o culegem
         // 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){
             // daca inaltimea la care avem gutuia < H
             // calculam nivelul gutuii
             kj = (H - h[j])/U + 1;
             if (kj > maxDone){
                // avem voie sa o culegem
                gMax += g[j];
                for (i = (H-h[j])/U + 1; i<k+1; i++){
                    picked[i] ++;
                    if (picked[i]==i && i>maxDone)
                       maxDone = i;
                }
            }
         }
         j++;        
     }
     
     free (g);
     free (h);
     free (picked);          
}

long pos(long left,long right){
    long i=left,j=right,direction=1;
    long aux;
    
    while (i<j){
       if (g[i]<g[j]){
          // facem swap intre cele doua jumatati
    	  aux=g[i];
    	  g[i]=g[j];
    	  g[j]=aux;
    	  aux=h[i];
    	  h[i]=h[j];
    	  h[j]=aux;
    	  if (direction==1) 
             direction=0;
          else 
             direction=1;
    	  }
       if (direction==1)
          j--;
       else 
          i++;
    }
    return i;

}
void quick(long left,long right){
    long k;
    if (left<right){
        k=pos(left,right);
        quick(left,k-1);
        quick(k+1,right);
    }
    return;
}