Cod sursa(job #440844)

Utilizator andreea149Andreea Pintilie andreea149 Data 12 aprilie 2010 16:29:11
Problema Gutui Scor 70
Compilator c Status done
Runda teme_upb Marime 3.75 kb
  //Pintilie Andreea    CA
  #include <stdio.h>
  #include <stdlib.h>
  #include <math.h>
   
  void merge(int* a, int* b,int * v, int low, int high, int mid, int N){
  int i, j, k, *c, *d,*f;
      c = (int * )malloc(N * sizeof(int) );
      d = (int * )malloc(N * sizeof(int) );
     f = (int * )malloc(N * sizeof(int) );
       i = low;
       j = mid+1;
       k = low;
           while( (i <= mid) && (j <= high) ){
                   if(a[i] > a[j]){
                       c[k] = a[i];
                       d[k] = b[i];   
                       f[k] = v[i];
                       k++;
                     i++;
                   }
                   else{
                       c[k] = a[j];
                       d[k] = b[j];
                       f[k] = v[j];
                       k++;
                       j++;
                   }
           }
          
           while(i <= mid){
               c[k] = a[i];
               d[k] = b[i];
               f[k] = v[i];
				k++;
               i++;
           }
            
           while(j <= high){
			                c[k] = a[j];
              d[k] = b[j];
               f[k] = v[j];
               k++;
               j++;
           }
           for(i = low; i < k; i++){
               a[i] = c[i];
               b[i] = d[i];
               v[i] = f[i];
         }
   free(c);
   free(d);   
   free(f);
   }
    
   void mergesort(int* a, int * b,int* v, int low, int high, int N){
   int mid;
       if(low < high){
           mid = (low+high)/2;
         mergesort(a,b,v, low, mid,N);
           mergesort(a,b,v, mid+1 , high,N);
           merge(a,b,v, low, high, mid,N);
       }
   }
    
   int main(){
   FILE *fin, *fout;
    
       fin = fopen("gutui.in", "r");
     fout = fopen("gutui.out", "w");
    
   int N, H, U, *h, *g, i, Gmax = 0, j, *v, *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 inaltimi si greutati
       h = (int * )malloc(N * sizeof( int ) );
       g = (int * )malloc(N * sizeof( int ) );
       v = (int * )malloc(N * sizeof( int ) );
        
   //citeste inaltimile si greutatile  
       for(i = 0; i < N; i++){
           fscanf(fin,"%d",&h[i]);
         fscanf(fin,"%d",&g[i]);
         if(H-h[i] >= 0){
           v[i]=(H-h[i])/U;}
           else{v[i]=-1;}
       }
       int max = 0;
       for(i = 0; i < N; i++){
          if(v[i] > max){
               max = v[i];
           }
        
       }
        
       if(N > max){
           max = N;
       }
   suma = (int *)malloc( (max + 1 ) * sizeof(int));
   //                 
    //sorteaza in functie de greutate
    mergesort(g,h,v,0,N-1 ,N);
     
    //afiseaza in fisierul de iesire ce a citit sortat in functi de inaltime
     
    for(i = 0; i <= max; i++)
    {
            suma[i] = 0;
        }
    
        for(i = 0; i <= max; i++){
            if(v[i] >= 0 && h[i] <= H){
            if(suma[v[i]] == 0){
                suma[v[i]] = g[i];
            }
            else{
                    j = v[i];
                    while(j >= 0 ){
                        if(suma[j] == 0){
                           suma[j] = g[i];
                            break;
                        }
                        else{
                            j = j -  1;
                        }
                         
                    }
            }
        }
       }
         
    //calculeaza Gmax adunand suma 
        for(i = 0; i <= max; i++){
            if(suma[i] != 0){
            Gmax = suma[i] + Gmax;
            }
        }
        fprintf(fout,"%d\n",Gmax);
         
   free(h);
    free(g);
    free(suma);
    fclose(fin);
    fclose(fout);
    return 0;
    }