Cod sursa(job #440295)

Utilizator cg1700Catalin Geosu cg1700 Data 11 aprilie 2010 23:35:00
Problema Gutui Scor 40
Compilator c Status done
Runda teme_upb Marime 3.55 kb
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

int main()
{
    FILE *f, *g;
    long int n;
    uint32_t h, u;
    uint32_t hg[100000], wg[100000], v_suma[100000], v_h[100000], v[100000];     //v_suma este folosit pentru a memora solutiile partiale ale problemei, v_h este folosit pentru a tine evidenta inaltimii pana la care putem sa culegem in momentul curent
    long int i = 0;
    long int j;
    long int x = 0;
    int ok;
    uint32_t aux;
    uint32_t min, max=0;

    f = fopen( "gutui.in", "r" );
    g=fopen( "gutui.out", "w" );
    fscanf( f, "%ld", &n );
    fscanf( f, "%d", &h );
    fscanf( f, "%d", &u );
    while(i<n)
       {
        fscanf( f, "%d", &hg[i] );
        fscanf( f, "%d", &wg[i] );
        if ( hg[i] > h )                          //conditie necesara ca programul sa nu citeasca si gutuile la inaltimi mai mari de h
           {
            wg[i] = 0;
            i--;
            n--;
           }
        i++;
       }

    for ( i = n - 1; i >= 0; i-- )                    //bubble sort ordoneaza descrescator gutuile dupa inaltime
       {
        for( j = 1; j <= i; j++ )
           if(hg[j-1]<hg[j])
              {
               aux = hg[j - 1];
               hg[j - 1] = hg[j];
               hg[j] = aux;
               aux = wg[j - 1];
               wg[j - 1] = wg[j];
               wg[j] = aux;
              }
        if( max < wg[n - i - 1] )                    //se determina greutatea maxima a unei gutui
           max = wg[n - i - 1];
        v[n - i]=0;
       }

    v_suma[0] = wg[0];                              //initializam prima solutie partiala cu greutatea gutuii care se afla cel mai sus si inaltimea curenta cu inaltimea maxima minus u
    v_h[0] = h - u;

    for( i = 1; i <= n; i++ )
       {
        ok = 0;
        if( hg[i] <= v_h[i - 1] )                  //daca gutuia curenta se afla la o inaltime mai mica decat cea maxima curenta adunam greutatea ei la solutia partiala anterioara
           v_suma[i] = v_suma[i - 1] + wg[i];
        else
           {
            min = max;                              //daca gutuia curenta se afla mai sus decat inaltimea maxima curenta programul determina gutuia cu greutate minima
            for( j = 0; j < i; j++ )                //dintre gutuile de pana atunci si daca aceasta greutate minima este mai mica decat greutatea curenta atunci
               if( v[j] == 0 )                      //inlocuim in solutia partiala anterioara gutuia cu greutate minima cu gutuia curenta, altfel solutia partiala ramane la fel
                  if( min > wg[j] )
                     {
                      min = wg[j];
                      x = j;
                     }
            if( min < wg[i] )
               {
                v[x] = 1;                                      //vectorul v are rolul de a tine minte gutuile care nu vor face parte din solutia finala dar sunt intalnite in calcularea solutiilor partiale
                v_suma[i] = v_suma[i - 1] + wg[i] - min;
               }
            else
               {
                v[i] = 1;
                v_suma[i] = v_suma[i - 1];
               }
           ok = 1;
          }
       if(( v_h[i - 1] > 0 )&&( ok == 0 ))
          v_h[i] = v_h[i - 1] - u;
       else                                                   //variabila ok ia valoare 1 in cazul in care nu este necesara scadera inaltimii maxime in pasul curent
          v_h[i] = v_h[i - 1];
      }

    fprintf( g, "%d", v_suma[n] );
    fclose(f);
    fclose(g);
    return 0;
}