Cod sursa(job #437733)

Utilizator cristinam.tanaseTanase Cristina cristinam.tanase Data 10 aprilie 2010 00:42:01
Problema Gutui Scor 0
Compilator cpp Status done
Runda teme_upb Marime 3.15 kb
  #include<stdio.h>


  struct gutu {
         int h;
         int g;
         };
 gutu gutui[100];        
         
    void quickSort(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)  
               quickSort(vect, stanga, j);  
         if (i < dreapta)  
              quickSort(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 );
     
          }
   
   
    
      
    quickSorth(gutui,0,N-1);
    
      
    i=0;
    int culese=0;
        while(i<N-1){
                stanga =i;
                k=0;
           while(gutui[i].h==gutui[i+1].h){
                 k++;
                 i++;
                 }
                 
                 i++;
               
                 if(k!=0){
                 quickSort(gutui,stanga, stanga+k);
                 
                 max--;
              
                 }      
                
                   }
                   
                   k=0;
          
          for( i = 0; i < N; i ++){
        
       if(k > max+1)
            break;
            else{
               if( k < gutui[i].h) {
                 
                   s=s+gutui[i].g;
                   k++;
                   }
                  
                   }     }      ;
 
     
 
fprintf(g,"%d",s);        
       
         return 1; 
     
             
    
}