Cod sursa(job #438219)

Utilizator gllbgllb gllb gllb Data 10 aprilie 2010 16:21:39
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 2.14 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 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);
}


int CanTakeFromTree(Gubbins g[], int N, unsigned int HRel, unsigned int H, unsigned int U)	
{							//functie care intoarce primul indice al gutuii care se poate lua din copac
	int i, j, ok = 0, index;
						
	for(j=0; j<N; j++)
		if(g[j].isInTree == 1)
			if( (g[j].height+HRel) <= H)
			{
				ok = 1; 
				break;
			}
	if( ok==0 )
		return -1;
	
	index = j;
	for(i=j+1; i<N; i++)
		if(g[i].isInTree == 1)
			if( g[i].height+HRel+U > H)    
				if(g[i].weight > g[index].weight)
					index = i;
	return index;

}

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, U)) >= 0 )
	{
		Gmax = Gmax + g[j].weight;
		g[j].isInTree = 0;
		HRel += U;
	}
	
	fprintf(f2,"%u\n",Gmax);
		
	fclose(f1);
	fclose(f2);
	return 0;
}