Cod sursa(job #441318)

Utilizator andreea149Andreea Pintilie andreea149 Data 12 aprilie 2010 21:10:02
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 2.25 kb
  //Pintilie Andreea    CA
  #include <stdio.h>
  #include <stdlib.h>
  #include <math.h>
 
 
   typedef struct Gutuie{
	int h; //retin inaltimea la care se afla
	int g; //retine greutatea la care se afla
	int v; //retine nivelul(cate gutui pot lua inaintea gutuii G[i])
}gut;
			
int cmp(const void *x, const void *y){
		
	return  ((gut *)y)->g  - ((gut *)x)->g;

}

int main(){
   FILE *fin, *fout;
     fin = fopen("gutui.in", "r");
     fout = fopen("gutui.out", "w");
	gut * G;
	int N, H, U,  i, Gmax = 0, j, *suma;
   //citeste nr de gutui  
       fscanf(fin,"%d",&N);
    
   //citeste inaltimea maxima
       fscanf(fin,"%d",&H);
        
   //citeste cu cat se ridica
		fscanf(fin,"%d",&U);
		
	//aloca memorie pentru suma	
     suma = (int *)malloc( (N + 1 ) * sizeof(int));

   //aloca memorie pentru inaltimi si greutati
       G = (gut * )malloc(N * sizeof( gut ) );        
   //citeste inaltimile si greutatile  
	for(i = 0; i < N; i++){
           fscanf(fin,"%d",&G[i].h);
           fscanf(fin,"%d",&G[i].g);
        //determina nivelul gutuii G[i]
        //stabileste daca pot lua mai multe gutui inaintea gutuii G[i] 
		if(H - G[i].h >= 0){
			G[i].v=(H-G[i].h)/U;
		//daca pot lua mai mult de N gutui setez nivelul ca fiind N+1(nu am mai mult de N gutui)	
			if(G[i].v >N){
				G[i].v = N + 1;
			}
		}
		//daca nu pot lua gutui inaintea lui G[i] setez vectorul nivel negativ
		if(H - G[i].h < 0){
			   G[i].v=-1;
		}
       }

	qsort( G, N, sizeof(gut),cmp);
	
        for(i = 0; i < N; i++){
            if(G[i].v >= 0){
            	if(suma[G[i].v] == 0){
                	suma[G[i].v] = G[i].g;
            	}
            	else{
                 	   j = G[i].v;
                		while(j >= 0 ){
                        	if(suma[j] == 0){
                           		suma[j] = G[i].g;
                            break;
                        	}
                        	else{
                           		 j = j -  1;
                        	}
                         
                		}
            	}
        	}
       	}
         
    //calculeaza Gmax adunand suma 
        for(i = 0; i <= N; i++){
            Gmax = suma[i] + Gmax;
        }
        fprintf(fout,"%d\n",Gmax);

   	free(G);
    free(suma);
    fclose(fin);
    fclose(fout);
    return 0;
    }