Cod sursa(job #438576)

Utilizator ionut.paraschivIonut Cristian Paraschiv ionut.paraschiv Data 10 aprilie 2010 21:19:47
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 2.56 kb
#include <stdio.h>

#define MAX_NUM 100000

typedef struct{
	unsigned int height;				//inaltimea la care se afla gutuia
	unsigned int weight;				//greutatea gutuii
} Gubbins;

void Merge(Gubbins *g, int p, int q)
{
	int len = q-p+1;
	Gubbins gub[len];
	int m = (p+q)/2;
	int i=p, j=m+1, k=0;
	while(i<=m && j<=q)
	{
		if(g[i].height == g[j].height)
		{
			if(g[i].weight > g[j].weight)	//daca 2 elemente au aceeasi inaltime, se sorteaza descrescator dupa greutate
				gub[k++] = g[i++];
			else
				gub[k++] = g[j++];
		}
		else if(g[i].height < g[j].height)
			gub[k++] = g[j++];
		else
			gub[k++] = g[i++];
	}
	while(i<=m)
		gub[k++] = g[i++];
	while(j<=q)
		gub[k++] = g[j++];
	for(i=0; i<len; i++)
		g[p+i] = gub[i];
}

void MergeSort(Gubbins *g, int p, int q)		//sortare descrescatoare dupa inaltime
{
	if(p == q)
		return;
	int m = (p+q)/2;
	MergeSort(g, p, m);
	MergeSort(g, m+1, q);
	Merge(g, p, q);
}



void UrcaValoarea(unsigned int *v, int poz)
{
	int parent=(poz-1)/2;
	unsigned int interm;
	if(parent>=0)	
	{
		if(v[parent]>=v[poz])
			return;
		else
		{
			interm = v[parent];
			v[parent] = v[poz];
			v[poz] = interm;
			UrcaValoarea(v, parent); 
		}
	}	
}

void addInVector(unsigned int *v, int size, unsigned int val)
{
	v[size] = val;
	UrcaValoarea(v, size);
}
void removeFirst(unsigned int *v, int i, int size)
{
	int l = (2*i+1), r = (2*i+2);
	if( l>=size && r>=size )
	{
		v[i] = 0;		//frunza
		return;	
	}
	else if (l<size && r>=size)
	{
		v[i] = v[l];
		removeFirst(v, l, size);
	}
	else if (l>=size && r<size)
	{
		v[i] = v[r];
		removeFirst(v, r, size);
	}
	else if(l<size && r<size)
	{
		if(v[l]>v[r])
		{
			v[i] = v[l];
			removeFirst(v, l, size);
		}
		else
		{
			v[i] = v[r];
			removeFirst(v, r, size);
		}
	}
}

int main()
{
	FILE *f1 = fopen("gutui.in","r"), *f2 = fopen("gutui.out","w");
	int N, i, vectorSize = 0, first_iter=1; 
	unsigned int H, U, Gmax = 0, HRel, vector[MAX_NUM];
	Gubbins g[MAX_NUM];
	fscanf(f1, "%d %u %u\n", &N, &H, &U);
	for(i=0; i<N; i++)
		fscanf(f1, "%u %u\n",&g[i].height, &g[i].weight);
	MergeSort(g, 0, N-1);
	if(H%U == 0)
		HRel = U;				//pozitia relativa pe ultimul nivel	
	else	
		HRel = H - ((H/U)*U);
	while( (HRel<=H) && (N>0 || vectorSize>0) )
	{
		if( vectorSize>0 )
		{
			Gmax += vector[0];
			removeFirst(vector, 0, vectorSize);
			HRel+=U;
		}
		else if(first_iter == 0)				
			HRel+=U;			//nu se adauga U la prima iteratie
		first_iter = 0;
		while(N>0)
		{
			if(g[N-1].height > HRel)
				break;
			addInVector(vector, vectorSize, g[N-1].weight);
			N--;
			vectorSize++;
		}
	}
	fprintf(f2,"%u\n",Gmax);
	fclose(f1);
	fclose(f2);
	return 0;
}