Cod sursa(job #434964)

Utilizator emilia.ciobanuCiobanu Emilia Maria Silvia emilia.ciobanu Data 6 aprilie 2010 19:26:59
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 1.87 kb
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>


#define IN "gutui1.in"
#define OUT "gutui.out"
#define MINF INT_MIN
#define PINF INT_MAX

typedef struct
{
	int h;
	int w;
	double r;
} GUTUIE;


void afisare (GUTUIE *G, int N)
{
	int i;
	for (i = 0 ; i < N; ++i)
		printf("Gutuia %d:\tinaltime: %d\t greutate: %d\t raport: %lf\n", i, G[i].h, G[i].w, G[i].r);
}

int compare (const void *a, const void *b)
{
	return (int)(1000*((GUTUIE*)b)->r)-(1000*((GUTUIE*)a)->r);
}

int cmph (const void *a, const void *b)
{
	return ((GUTUIE*)b)->h-((GUTUIE*)a)->h;
}

int comp (const void *a, const void *b)
{
	return compare(a, b) * cmph(a,b);
}

int cmpw (const void *a, const void *b)
{
	return ((GUTUIE*)b)->w-((GUTUIE*)a)->w;
}

int main (int argc, char **argv)
{
	int N, H, U, i, G = 0, Hmin = PINF;
	GUTUIE *g;

	FILE *fin  = fopen (IN, "r");
	FILE *fout = fopen (OUT, "w");

	fscanf (fin, "%d%d%d", &N, &H, &U);

	g = (GUTUIE*) calloc (N, sizeof(GUTUIE));

	for (i = 0; i < N; ++i)
	{
		fscanf(fin, "%d%d", &g[i].h, &g[i].w);
		g[i].r = (double)g[i].w/((double)H - (double)g[i].h);
		if ( Hmin > g[i].h )
			Hmin = g[i].h;
	}


	//printf( "Hmin : %d\n", Hmin );

	qsort (g, N, sizeof (GUTUIE), compare);

	//afisare (g, N);
	//printf("\n");

	int index, cnt = 0;
	double aux;

	while ( Hmin + 10*cnt <= H )
	{
		index = 0;
		do
		{
			if (g[index++].h + cnt*10 <= H)
				break;
		}
		while (index < N-cnt);

		cnt++;
		index--;

		//printf("%d\n", index);
		G += g[index].w;

		g[index].r = MINF;
		{
			g[index].w ^= g[N-cnt].w;
			g[N-cnt].w ^= g[index].w;
			g[index].w ^= g[N-cnt].w;

			g[index].h ^= g[N-cnt].h;
			g[N-cnt].h ^= g[index].h;
			g[index].h ^= g[N-cnt].h;

			aux = g[index].r;
			g[index].r = g[N-cnt].r;
			g[N-cnt].r = g[index].r;
		}

		qsort (g, N-cnt, sizeof(GUTUIE), compare);

		//afisare (g, N-cnt);
	}

	printf("%d\n", G);

	free(g);
	fclose(fin);
	fclose(fout);

	return 0;
}