Cod sursa(job #463767)

Utilizator simona.poilincaSimona Poilinca simona.poilinca Data 17 iunie 2010 13:33:50
Problema Gutui Scor 80
Compilator c Status done
Runda teme_upb Marime 2.42 kb
#include <stdio.h>
#include <stdlib.h>

int N, H, U;

typedef struct gutuie {
        
        int h; // inaltime
        int g; // greutate
        int prior; // var folosita pt vectorul v, prioritate
        
        } gutui;

gutui *G; // vectorul de gutui date
gutui * v;  // vectorul cu gutui luate
int size; // nr de valori alocate pt v

void citire (FILE *f) {
     
     fscanf(f,"%d %d %d", &N, &H, &U);
     G = (struct gutuie *)malloc(N*sizeof(struct gutuie));
     v = (struct gutuie *)malloc(N*sizeof(struct gutuie)); 
     int i;
     for(i=0; i<N; i++) 
              fscanf(f,"%d %d", &G[i].h, &G[i].g);  
     for(i=0; i<N; i++) 
              v[i].prior = -1; // nicio gutuie luata     
	    
     }



int poz (int h, int H, int U) { // pozitia reala in vectorul v
    
    int c = -1;
    if (h > H) 
       c = 0;
    while (h <= H) {
          h += U;
          c++;
          }   
    return c;
    }


int pozitie (int s, int d) { // sortare descrescatoare dupa greutate

	int i=s, j=d, di=0, dj=1;
	gutui aux;
	while(i < j)
		{ if(G[i].g < G[j].g)
			{ aux=G[i];
			  G[i]=G[j];
			  G[j]=aux;
			  di=1-di;
			  dj=1-dj; }
		  i+=di;
		  j-=dj; }
        return i;
}


void quick (int s, int d) {

	if(s < d) { 
		int k = pozitie(s,d);
		quick(s,k-1);
		quick(k+1,d); }
}


int pune (gutui G, int p) { 
     
     if (G.h > H) return 0;
     else {
          if(v[p].prior == -1) { // loc gol
                        v[p] = G;
                        v[p].prior = p;
			return G.g; }
          else {
                int j = p -1 ;
                while (j>=0 && v[j].prior != -1) 
                      j--;
                // a gasit pozitie libera
		if( j >= 0) {               
			v[j] = G;
			v[j].prior = j; 
			return G.g; }
               }              
          }
     return 0;
   
     } 

int main (int argc, char ** argv) {
    
         FILE * f = fopen("gutui.in", "r");
         FILE * g = fopen ("gutui.out", "w");
         citire (f);
         quick(0,N-1);
   	 int i, s, suma = 0;
	 
         for (i=0; i<N; i++) {
             int p = poz (G[i].h, H, U);
	     s = pune(G[i], p) ; // pune in vectorul v, cu prioritatea p, Gutuia i
	     suma += s;
             }
         
         fprintf(g,"%d", suma);    
              
         fclose(f);
         fclose(g);
	 free(G);
	 free(v);
         return 0;
    
    }