Cod sursa(job #463341)

Utilizator simona.poilincaSimona Poilinca simona.poilinca Data 15 iunie 2010 02:50:51
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 2.68 kb
  //Pintilie Andreea    CA
  #include <stdio.h>
  #include <stdlib.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;

//functia comparator			
int cmp(const void *x, const void *y){

	//sorteaza descrescator		
	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;
		}
       }

	//sorteaza descrescator in functie de greutati
	qsort( G, N, sizeof(gut),cmp);

		//adauga greutatile in vectorul suma	
        for(i = 0; i < N; i++){
			//doar daca nivelul este mai mare sau egal cu 0 va putea adauga	
            if(G[i].v >= 0){
				//daca a gasit pozitie libera in vectorul suma, adauga greutatea
            	if(suma[G[i].v] == 0){
                	suma[G[i].v] = G[i].g;
            	}
            	//altfel cauta pozitie in vectorul suma
            	else{
                 	   j = G[i].v;
                 	   //cat timp nu a gasit pozitie
                		while(j >= 0 ){
							//a gasit pozitie libera, adauga greutatea si iese din while
                        	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);

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