Cod sursa(job #436810)

Utilizator marina.cioceaMarina Ciocea marina.ciocea Data 8 aprilie 2010 23:29:24
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 1.85 kb
#include<stdio.h>
#include<stdlib.h>

typedef struct{
	unsigned int height, weight;			
} Gutuie;

int compareH (const void * a, const void * b)
{
    Gutuie *g1=(Gutuie *)a;
    Gutuie *g2=(Gutuie *)b;
    return (g2->height) - (g1->height);
}

int compareV (const void * a, const void * b)
{
    Gutuie *g1=(Gutuie *)a;
    Gutuie *g2=(Gutuie *)b;
    return (g2->weight) - (g1->weight);
}

int main()
{
	int  N=0, H=0, U=0, i, hHeight, hValue, max, sumH=0, sumV=0;
	Gutuie *gutui, *inaltime, *value;
	

	FILE * in = fopen("gutui.in", "r");
	if(in==NULL)
		return;	

	fscanf(in, "%d", &N);
	fscanf(in, "%d", &H);
	fscanf(in, "%d", &U);
//	printf("%d %d %d\n",N, H, U);
	
	gutui=(Gutuie*)malloc(N*sizeof(Gutuie));
	inaltime=(Gutuie*)malloc(N*sizeof(Gutuie));
	value=(Gutuie*)malloc(N*sizeof(Gutuie));
	
	for(i=0; i<N; i++)
	{
		fscanf(in, "%d", &gutui[i].height);
        fscanf(in, "%d", &gutui[i].weight);
        inaltime[i]=gutui[i];
        value[i]=gutui[i];
//		printf("h: %d  w:  %d\n", gutui[i].height, gutui[i].weight);
	}
//	printf("\n");
	fclose(in);
	
	qsort (inaltime, N, sizeof(Gutuie), compareH);
	qsort (value, N, sizeof(Gutuie), compareV);
	
/*	for(i=0; i<N; i++)
	{
		printf("h: %d  w:  %d\n", inaltime[i].height, inaltime[i].weight);
	}
	printf("\n");
	for(i=0; i<N; i++)
	{
		printf("h: %d  w:  %d\n", value[i].height, value[i].weight);
	}
	printf("\n");
	*/
	hHeight=H;
	hValue=H;
	
	for(i=0; i<N; i++)
	{
		if(hHeight >= inaltime[i].height)
		{
			sumH+=inaltime[i].weight;
			hHeight-=U;
		}
		if( hValue >= value[i].height)
		{
			sumV+=value[i].weight;
			hValue-=U;	
		}
    }
	max=sumH;
	if(sumV>max)
		max=sumV;
//	printf("max:%d \n", max);
	FILE * out = fopen("gutui.out", "w");
	fprintf(out, "%d", max);
	fclose(out);
	
//	getch();
	free(gutui);
	return 0;
    

}