Cod sursa(job #434675)

Utilizator dragosiordachedragos iordache dragosiordache Data 6 aprilie 2010 13:38:31
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 1.08 kb
#include "stdio.h"
int h,u;


typedef struct {
	int h,g;
	int val;
} gutui;

int cmp(void* a, void* b)
{
	int x = (((gutui*)b)->h)/u - (((gutui*)a)->h)/u;
	return (x?x:(((gutui*)b)->g - ((gutui*)a)->g));
}

int cmp2(void* a, void* b)
{
	return ((((gutui*)b)->g - ((gutui*)a)->g));
}

int main() 
{
	FILE *f, *g;
	f = fopen("gutui.in", "r");
	g = fopen("gutui.out", "w");
	int n,i;

	fscanf(f, "%i %i %i", &n,&h,&u);
	gutui a[n];
	gutui b[n];

	for (i=0;i<n;i++)
		fscanf(f, "%i %i", &a[i].h, &a[i].g);

	qsort(a, n, sizeof(gutui), cmp);

	int j=0,   //numarul de gutui din grupul curent
		 k=1;   //numarul grupului curent

	int m=0;
	i=0; 
	while(i<n)
	{
		if (a[i].h > h-k*u)
		{
			if (j>=0)
			{
				b[m] = a[i];
				b[m++].val = j;
				j--;
			}
			i++;
		}
		else
		{
			j=k++;
		}
	}

	qsort(b, m, sizeof(gutui), cmp2);
	
	int c[n];
	for (j=0;j<n;j++)
		c[j]=-1;
	int tot=0;
	for (j=0;j<m;j++)
	{
		if (c[b[j].val]<b[j].val+1)
		{
			tot+=b[j].g;
			printf("%i %i\n", b[j].h, b[j].g);
			c[b[j].val]++;
		}
	}
	fprintf(g, "%i", tot);

	printf("%i\n", tot);

	close(f);
	close(g);
	
	return 0;
}