Cod sursa(job #437815)

Utilizator cristinam.tanaseTanase Cristina cristinam.tanase Data 10 aprilie 2010 02:49:02
Problema Gutui Scor 0
Compilator cpp Status done
Runda teme_upb Marime 3.33 kb
  #include<stdio.h>
//  #include<conio.h>

  struct gutu {
         int h;   //inaltime
         int g;   //greutate
         int p;   //prioritate
         };
 gutu gutui[10000];        
     int oc[10000];    
    void quickSortG(gutu vect[], int stanga, int dreapta) {  
       int i = stanga, j = dreapta;  
          gutu tmp;  
          int pivot = vect[(stanga + dreapta) / 2].g;  
          while (i <= j) {  
                while (vect[i].g > pivot)  
                      i++;  
                while (vect[j].g < pivot)  
                      j--;  
               if (i <= j) {  
                     tmp = vect[i];  
                     vect[i] =vect[j];  
                     vect[j] = tmp;  
                     i++;  
                     j--;  
               }  
          
         };  
         if (stanga < j)  
               quickSortG(vect, stanga, j);  
         if (i < dreapta)  
              quickSortG(vect, i, dreapta);  
   }  
   
     void quickSorth(gutu vect[], int stanga, int dreapta) {  
       int i = stanga, j = dreapta;  
          gutu tmp;  
          int pivot = vect[(stanga + dreapta) / 2].h;  
          while (i <= j) {  
                while (vect[i].h < pivot)  
                      i++;  
                while (vect[j].h > pivot)  
                      j--;  
               if (i <= j) {  
                     tmp = vect[i];  
                     vect[i] =vect[j];  
                     vect[j] = tmp;  
                     i++;  
                     j--;  
               }  
         };  
         if (stanga < j)  
               quickSorth(vect, stanga, j);  
         if (i < dreapta)  
              quickSorth(vect, i, dreapta);  
   }  
   
    
   int main(){
       
    FILE *f,*g;
    int N, H, U, i, auxh,pondere[100],max=0,iaics[100],k,s,stanga;
    f = fopen( "gutui.in", "r" );
    g = fopen( "gutui.out", "w" );
    fscanf(f, "%d", &N);
    fscanf(f, "%d", &H);
    fscanf(f, "%d", &U);
    
     for( i = 0; i < N; i ++){       
           fscanf ( f, "%d", &auxh );
          gutui[i].h=(H-auxh)/U+1;
          if(gutui[i].h > max)
             max=gutui[i].h;
        
          fscanf ( f, "%d", &gutui[i].g );
     
          }
   
    
      
    quickSortG(gutui,0,N-1);
    
  int ind,j;
  int cules=1;
   i=0;
  int ok=1;
   while(i<N && ok==1){
              if(oc[gutui[i].h]==0){
                                oc[gutui[i].h]=1;
                                gutui[i].p=gutui[i].h ; 
                                s=s+gutui[i].g;
                                }
                                else { ind=gutui[i].h;
                                     while(oc[ind]!=0 && ind>0 )
                                        ind--;
                                        if(ind>0){
                                        oc[ind]=1;
                                        gutui[i].p=ind;
                                        s=s+gutui[i].g;}
                                        else 
                                        ok=0;}                                
                                i++;
                                }
       
   
      
      
   
 
        

fprintf(g,"%d",s);        
        // getch();
         return 0; 
     
             
    
}