Cod sursa(job #438425)

Utilizator gllbgllb gllb gllb Data 10 aprilie 2010 18:58:42
Problema Gutui Scor 80
Compilator c Status done
Runda teme_upb Marime 2.64 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 addInVector(unsigned int *v, int N, unsigned int val)
{
	int i, j, ok=0;
	if(N==0)
		v[0] = val;
	else if(N==1)
	{
		if(v[0]>=val)
			v[1] = val;
		else
		{
			v[1] = v[0];
			v[0] = val;
		}
	}
	else
	{
		if(val > v[0])
		{
			for(i=N; i>=1; i--)
				v[i] = v[i-1];
			v[0] = val;
		}
		else
		{
			for(i=0; i<N-1; i++)
			{
				if( (val<=v[i]) && (val>=v[i+1]) )
				{
					for(j=N; j>i; j--)
						v[j] = v[j-1];
					v[i+1] = val;
					ok=1;
					break;
				}
			}
		if(ok == 0)
			v[N++] = val;
		}
	}
}
void removeFirst(unsigned int *v, int N)
{
	int i;
	for(i=1; i<N; i++)
		v[i-1] = v[i];
}

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);
	
	/*for(i=0; i<N; i++)
		printf("%u %u\n", g[i].height, g[i].weight);*/
	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];
			//printf("Se adauga %d\n",vector[0]);
			removeFirst(vector, vectorSize);
			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;
			//printf("Se adauga in vector %d..   =>    ",g[N-1].weight);
			addInVector(vector, vectorSize, g[N-1].weight);
			N--;
			vectorSize++;
			/*int j;
			for(j=0; j<vectorSize; j++)
				printf("%d ",vector[j]);
			printf("\n");*/ 
			
		}


	}
	printf("%d\n",Gmax);
	fprintf(f2,"%u\n",Gmax);
	fclose(f1);
	fclose(f2);
	return 0;
}