Cod sursa(job #438193)

Utilizator gllbgllb gllb gllb Data 10 aprilie 2010 15:52:17
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 1.93 kb
#include <stdio.h>

#define MAX_NUM 100000

typedef struct{
	unsigned int height;				//inaltimea la care se afla gutuia
	unsigned int weight;				//greutatea gutuii
	char isInTree;		                        //0 daca nu e in copac, 1 altfel	
} 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 greutate, se sorteaza descrescator dupa inaltime
				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 greutate
{
	if(p == q)
		return;
	int m = (p+q)/2;
	MergeSort(g, p, m);
	MergeSort(g, m+1, q);
	Merge(g, p, q);
}
int CanTakeFromTree(Gubbins *g, int N, unsigned int HRel, unsigned int H)	
{							//functie care intoarce primul indice al gutuii care se poate lua din copac
	int j;
	for(j=0; j<N; j++)
		if(g[j].isInTree == 1)
			if( (g[j].height+HRel) <= H) 
				return j;
			
	return -1;
}

int main()
{
	FILE *f1 = fopen("gutui.in","r"), *f2 = fopen("gutui.out","w");
	int N, i, j; 
	unsigned int H, U, Gmax = 0, HRel = 0;
	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);
		g[i].isInTree = 1;
	}
	/*for(i=0; i<N; i++)
		printf("%u %u   %d\n", g[i].height, g[i].weight, g[i].isInTree);*/
	MergeSort(g, 0, N-1);
	
	/*printf("\n");
	for(i=0; i<N; i++)
		printf("%u %u\n", g[i].height, g[i].weight);
	*/
	while( (j = CanTakeFromTree(g, N, HRel, H)) >= 0 )
	{
		Gmax = Gmax + g[j].weight;
		g[j].isInTree = 0;
		HRel += U;
	}
	/*printf("%u\n",Gmax);*/
	fprintf(f2,"%u\n",Gmax);
		
	fclose(f1);
	fclose(f2);
	return 0;
}