Cod sursa(job #442692)

Utilizator biancaLBianca Leuca biancaL Data 14 aprilie 2010 23:13:54
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 3.51 kb
# include <stdio.h>
#include <stdlib.h>
# define MAXW 2147483647

typedef struct gutuie { int h, w;} TGutuie;

void mergeS ( TGutuie** A ,int  p, int q, int r )
{
      int n1, n2, i, j, k;
      n1  = q - p;
      n2 = r - q;
      TGutuie h1 [n1 + 1], h2[n2 + 1];
      for ( i = 0; i < n1; i ++ )
          h1[i] = (*A)[ p + i ];
          for ( j = 0; j < n2; j++ )
              h2[j] = (*A) [ q + j];
      h1[n1].h = MAXW;
      h2[n2].h = MAXW;
      i = 0; 
      j = 0;
      for ( k = p; k < r; k++ )
      if ( h1[i].h <= h2[j].h )
         {
         (*A)[k] = h1[i];
         i++;
         }
         else
         {
             (*A)[k] = h2[j];
             j++;
         }
}
void merge_sort ( TGutuie** A,int  p,int  r)
  {
     int q;
           if ( p + 1 == r )
              return;
              q = ( p + r )/ 2;
              merge_sort ( A, p, q );
              merge_sort ( A, q, r );
              mergeS ( A, p, q, r );
  }            
                             

int main()
{
FILE *f1 = fopen ("gutui.in", "rt" );
FILE *f2 = fopen ("gutui.out", "wt");

 if ( !f1 || !f2 )
   {
    fprintf ( f2, "eroare la deschiderea fisierelor ");
    return -1;
   }
     
int N, U, H, nr = 0, i, j, greutateMax = 0, inaltime = 0,k;


    fscanf (f1, "%i%i%i",&N, &H, &U); 
    TGutuie *gutui, culese[N],a;
    gutui = (TGutuie*)malloc(N*sizeof(TGutuie));
    for ( i = 0; i < N; i++)
    fscanf (f1, "%i%i", &(gutui[i].h), &(gutui[i].w) );

// sortare
merge_sort ( &gutui, 0, N );
/*for ( i = N-1; i >= 0; i--)
printf ("%i %i\n" , gutui[i].w, gutui[i].h);*/

//scanf("%i", &N);
for ( i = N-1; i >= 0; i-- )
  {
  if ( gutui[i].h + inaltime <= H )     
  {
  culese[nr] = gutui[i];
  inaltime = inaltime + U;
  j = nr;
  while ( j != 0 && culese[(j-1)/2].w > culese[j].w )
        {
        a = culese[( j - 1 )/2];
        culese[(j-1)/2] = culese[j];
        culese[j] = a;
        j = ( j - 1 )/2;
        }
        nr++;
   }
   else
   {
   if ( culese[0].w < gutui[i].w )
      {
      culese[0] = gutui[i];
      j = 0;
      while ( 2*j + 1 < nr )
      {
        if( 2*j + 2 < nr )
            if ( culese[2*j + 1].w <= culese[2*j + 2].w )
             {
               if ( culese[j].w > culese[2*j + 1].w)
               {
               a = culese[2*j +1];
               culese[2*j +1] = culese[j];
               culese[j] = a;
               j = 2*j +1;
               }
               
               else
                   break;
             } 
             else
               {
               if ( culese[j].w > culese[2*j + 2].w)
               {
               a = culese[2*j +2];
               culese[2*j +2] = culese[j];
               culese[j] = a;
               j = 2*j +2;
               }
               else
                   break;
             } 
             else
             {
                if ( culese[j].w > culese[2*j + 1].w)
               {
               a = culese[2*j +1];
               culese[2*j +1] = culese[j];
               culese[j] = a;
               j = 2*j +1;
               }
               
               else
                   break;
             }    
    }         
}
}
/*for ( k = 0; k < nr; k++ )
printf ( "%i ",culese[k].w);
printf ( "\n");
*/
}
for ( i = 0; i < nr; i++ )
    greutateMax = greutateMax + culese[i].w;                   
  
     
  
  
  
 
fprintf(f2,"%i", greutateMax);
free(gutui);
fclose(f1);
fclose(f2);
//getch();
return 0;
}