Cod sursa(job #463384)

Utilizator simona.poilincaSimona Poilinca simona.poilinca Data 15 iunie 2010 16:36:06
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 2.3 kb
//Pirvan Anca 325CA


//s=vectorul unde bag gutuile pe care le culeg
//H-inaltimea maxima la care ajunge Gigel
//U-cu cat se ridica crengile
//g-greutate fruct
//h-inaltime fruct
//N-nr gutui


#include<stdio.h>
#include<stdlib.h>

typedef struct gut
{
	int h;
	 int g;
}gutuie;


int compare(const void*x,const void* y)
{
	if((*(gutuie*)x).h == (*(gutuie*)y).h)
		return ( (*(gutuie*)x).g - (*(gutuie*)y).g ) ;
	else
		return  -((*(gutuie*)x).h-(*(gutuie*)y).h);
}

//functie care schimba radacina si o coboara 
void coboara( int *s, int i, int dim) // dim=dimensiune
{	
	if (dim==1) return;
	 int stg = 2*i+1;
	 int dr = 2*i+2;
	 int min;
	if(stg <dim && s[stg]<s[i])
		min=stg;
	else
		min=i;
	if(dr < dim && s[dr]<s[min])
		min=dr;
	 int aux = s[i];
	s[i] = s[min];
	s[min] = aux;
	
	if (i == min)
		return;
	else
		coboara(s,min,dim);
}
//functie care sterge un element din heap
void sterge( int *s,  int *dim) {
	s[0] = s[--(*dim)];
	coboara (s,0,*dim);
}
void ridica ( int *s, int poz, int dim) {
	int parinte = (poz-1)/2;
	 int aux;
	if (s[parinte]>s[poz]) {
		aux = s[parinte];
		s[parinte] = s[poz];
		s[poz] = aux;
		ridica(s,parinte,dim);
	}
}
//functie care insereaza pe ultimul loc si ridica elementul
void insereaza( int *s, int *dim,  int x)
{
	int poz = *dim;
	s[poz] = x;
	(*dim)++;
	ridica(s,poz,(*dim));
}

int main()
{
	FILE *f,*g;
	f=fopen("gutui.in","r");
	g=fopen("gutui.out","w");
	int N;
	int H;
	int U;
	int s[100000]; //heap
	int i;
	int dim_heap;
	long int sum=0; //suma greutatilor
	gutuie x[100000];
	fscanf(f,"%d",&N);
	fscanf(f,"%d",&H);
	fscanf(f,"%d",&U);
	dim_heap=0;
	for(i=0;i<N;i++)
	{
		fscanf(f,"%d",&(x[i].h));
		fscanf(f,"%d",&(x[i].g));
	}
	
	//sortez descrescator dupa inaltime
	qsort(x, N, sizeof(gutuie), compare); 	
	for (i=0; i<N;++i) 
		if (x[i].h <= H) 
		{
			insereaza(s,&dim_heap,x[i].g);
			H-=U;
			break;
		}
	for (i++;i<N;++i) {
		if (x[i].h > H && x[i].g > s[0]) 
		{
			sterge(s,&dim_heap);
			insereaza(s,&dim_heap,x[i].g);
		}
		if (x[i].h <= H) 
		{
			insereaza(s,&dim_heap,x[i].g);
			H-=U;
		}
	}
	//calculez suma greutatilor
	for (i=0;i<dim_heap;++i)
	{
		sum+=s[i];
	}
//scriu suma in fisier
fprintf(g,"%lu\n",sum);
	
fclose(f);
fclose(g);
return 0;
}