Cod sursa(job #438184)

Utilizator MariaPOPMaria Popoviciu MariaPOP Data 10 aprilie 2010 15:48:58
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 3.19 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;
}