Cod sursa(job #438205)

Utilizator MariaPOPMaria Popoviciu MariaPOP Data 10 aprilie 2010 16:06:55
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 3.69 kb
#include <stdio.h>
#include <malloc.h>

const char *fin = "gutui.in";
const char *fout = "gutui.out";

// N = numar de gutui din copac
// H = inaltimea la care poate ajunge culegatorul
// U = inaltimea cu care se ridica crengile dupa culegerea unei gutui
// pg = pointer catre vectorul maselor gutuilor
// ph = pointer catre vectorul inaltimilor la care se afla gutuile
// GG = masa totala a gutuilor culese

int N, H, U, GG;
int *pg, *ph;

// Functie pentru citirea datelor de intrare: N, H, U

void readn()
{
     FILE *f;
     
     f = fopen( fin, "r" );
     fscanf( f, "%d %d %d", &N, &H, &U);
     fclose( f );  
}

// Functie pentru citirea din fisierul gutui.in a vectorilor inaltimilor si
// greutatilor 

void readf( int *pg, int *ph )
{
     FILE *f;
     int i, j;
     
     f = fopen( fin, "r" );
     fscanf( f, "%d %d %d", &N, &i, &j);
     for( i = 0 ; i < N ; i++ )
     fscanf( f, "%d %d", ph + i, pg + i);
     fclose( f );
}

// Functie pentru scrierea solutiei in fisierul gutui.out
 
void writef()
{
     FILE *f;
     
     f = fopen( fout, "w" );
     fprintf( f, "%d", GG );
     fclose( f );
} 

// Functia de sortare prin metoda quicksort

void quicksort( int pg[], int ph[], int st, int dr ) 
{
     int aux1, aux2, salvst, salvdr; 
  
     salvst = st;
     salvdr = dr;
     aux1 = pg[st];
     aux2 = ph[st];
     while( st < dr ){
            while(( pg[dr] >= aux1 ) && ( st < dr ))
            dr--;
            if( st != dr ){
                pg[st] = pg[dr];
                ph[st] = ph[dr];
                st++;
            }
            while(( pg[st] <= aux1 ) && ( st<dr )) 
            st++;
            if( st != dr ){
                  pg[dr] = pg[st];
                  ph[dr] = ph[st];
                  dr--;
            }
     }
     pg[st] = aux1;
     ph[st] = aux2;
     aux1 = st;
     aux2 = st;
     st = salvst;
     dr = salvdr;
     if( st < aux1 )
                quicksort( pg, ph, st, aux1 - 1 );
     if( dr > aux1 )
                quicksort( pg, ph, aux1 + 1, dr );
}
 
// Initializare vector la adresa p cu 0

void init(int *p)
{
     int i;
     
     for( i = 0 ; i < N ; i++ )
     *(p + i)=0;
}

// Functie care determina prima pozitie cu indice maxim aflata inaintea 
// indicelui poz cu valoare 0

int max( int v[], int n, int poz )
{
    int i;
    
    for( i = 0 ; i < poz ; i++ )
    if( v[poz-i-1] == 0 ) break;
    return poz-i-1;
}

// Functie pentru constructia vectorului nivelelor gutuilor 
// v reprezinta vectorul pozitiilor libere la un moment dat
// (H+U-*(ph+i))/U reprezinta nivelul urmator al gutuilor

void nivele( int *ph, int *nivel )
{   
    int i,*v;
    
    v = (int *)malloc( N*sizeof(int) );
    init( v );
    for( i = N-1 ; i >= 0 ; i-- ){
         *(nivel + i) = (H + U- *(ph + i))/U; 
         if( *(nivel + i) < 1 ) break;
         if( *(v + ( *(nivel + i) - 1)) == 0 )
         *(v + (*( nivel + i )-1 )) = 1;
         else {
              *( nivel + i ) = 1 + max( v, N, *(nivel + i)-1 );
              *(v+ (*(nivel+i)-1)) = 1;
         }
     }
}
 
// Functie pentru culegere gutui

int culeg( int *p, int *vmase )
{
    int i, masa;
    
    for( masa = 0 , i = 0 ; i < N ; i++ )
    if( *( p + i ) > 0 )
    masa + = *( vmase + i );
    return masa;
}
             
int main()
{
    int *nivel;
    
    readn();
    ph = (int *)malloc( N*sizeof( int ));
    pg = (int *)malloc( N*sizeof( int ) );
    nivel = (int *)malloc( N*sizeof( int ) );
    readf( pg, ph );
    quicksort( pg, ph, 0, N - 1 );
    init( nivel );
    nivele( ph, nivel );
    GG = culeg( nivel, pg );
    writef();
    return 0;
}