Cod sursa(job #436950)

Utilizator cristinam.tanaseTanase Cristina cristinam.tanase Data 9 aprilie 2010 01:48:35
Problema Gutui Scor 0
Compilator cpp Status done
Runda teme_upb Marime 2.99 kb
  #include<stdio.h>
  #include<conio.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 quickSort1(int vect[], int stanga, int dreapta) {  
       int i = stanga, j = dreapta;  
          gutu tmp1; 
          int tmp ;
          int pivot = vect[(stanga + dreapta) / 2];  
          while (i <= j) {  
                while (vect[i] < pivot)  
                      i++;  
                while (vect[j] > pivot)  
                      j--;  
               if (i <= j) {
                     tmp1=gutui[i];  
                     tmp = vect[i];  
                     gutui[i]=gutui[j];
                     vect[i] =vect[j]; 
                     gutui[j]=tmp1; 
                     vect[j] = tmp;  
                     i++;  
                     j--;  
               }  
         };  
         if (stanga < j)  
               quickSort1(vect, stanga, j);  
         if (i < dreapta)  
              quickSort1(vect, i, dreapta);  
   }  

  
  int main(){
      
    FILE *f,*g;
    int N, H, U, i, auxh,pondere[100],max,iaics[100],k,s;
    f = fopen( "gutui.in", "r" );
    g = fopen( "gutui.out", "w" );
    fscanf(f, "%d", &N);
    fscanf(f, "%d", &H);
    fscanf(f, "%d", &U);
    max = 0;
  
    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 );
     
          }
   
   quickSort(gutui,0,N-1);
  
   pondere[ N -1 ]= 1;
   iaics[ N -1 ]= gutui[ N - 1 ].h;
   k=1;
   for( i = N - 2; i >= 0; i --){
       if(gutui[i].g != gutui[i+1].g)
                     pondere[i]=++k;
                     else
                     pondere[i]=k;
        iaics[i]=pondere[i]+gutui[i].h;
        }

   quickSort1(iaics,0,N-1);
  
   
   k=0;
   s=0;
    for( i = 0; i < N; i ++)
       if(k > max)
            break;
            else{
               if( k <= gutui[i].h) {
   
                   s=s+gutui[i].g;
                   k++;
                   }
     
                   }           

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