Cod sursa(job #434982)

Utilizator copotalex copot Data 6 aprilie 2010 19:42:45
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 3.21 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct {
	unsigned int h;
	unsigned int g;
	char used;
} gutuie;

gutuie vg[100000];
int N, H, U;

void citeste()
{
	FILE *f = fopen("gutui.in", "rt");
	int i;
	if ( f == NULL )
		return;
		
	fscanf(f, "%d%d%d", &N, &H, &U);
	for (i = 0; i < N; i++)
		fscanf(f, "%d%d", &vg[i].h, &vg[i].g);
	fclose(f);
}

int comp1(const void *s1, const void *s2)
{
	return ((gutuie*)s2)->g - ((gutuie*)s1)->g;
	//return (float) ((gutuie*)s2)->g / ((gutuie*)s2)->h - (float) ((gutuie*)s1)->g / ((gutuie*)s1)->h;
}

int comp2(const void *s1, const void *s2)
{
	//return ((gutuie*)s2)->h - ((gutuie*)s1)->h;
	return (float) ((gutuie*)s2)->g / ((gutuie*)s2)->h - (float) ((gutuie*)s1)->g / ((gutuie*)s1)->h;
}

int comp3(const void *s1, const void *s2)
{
	return ( H - ((gutuie*)s1)->h ) / U - ( H - ((gutuie*)s2)->h ) / U;
	//return (float) ((gutuie*)s2)->g / ((gutuie*)s2)->h - (float) ((gutuie*)s1)->g / ((gutuie*)s1)->h;
}

int comp4(const void *s1, const void *s2)
{
	return ((gutuie*)s2)->h - ((gutuie*)s1)->h;
	//return (float) ((gutuie*)s2)->g / ((gutuie*)s2)->h - (float) ((gutuie*)s1)->g / ((gutuie*)s1)->h;
}

int main(int argc, char **argv)
{
	int maxg, sol;
	unsigned int i, ncmax, ncmin, im, nci, alese, mnext, sg;
	
	citeste();

	qsort(vg, N, sizeof(gutuie), comp1); 
	
	i = 0;
	ncmax = 0; // cate gutui voi culege
	while (i < N) {
	  if ( (H - vg[i].h) / U + 1 > ncmax )
	    ncmax = (H - vg[i].h) / U + 1;
		i++;
	}
	printf("ncmax %d\n", ncmax);
	sol = 0;	
	for (i = 0; i < N; i++)
		printf("%d %d -> %d\n", vg[i].h, vg[i].g, (H - vg[i].h) / U + 1);
/*
	alese = 0;
	sol = 0;
	for (i = 0; i < N; i++) {
	  if ( vg[i].h + alese * U > H )
		break;
	  sol += vg[i].g;
	  
	  alese++;
	}
	
	ncmax = sol;
	qsort(vg, N, sizeof(gutuie), comp4); 
	

	alese = 0;
	sol = 0;
	for (i = 0; i < N; i++) {
	  if ( vg[i].h + alese * U > H )
		break;
	  sol += vg[i].g;
	  
	  alese++;
	}
	if ( sol > ncmax )
		ncmax = sol;
	
*/
/*
	nci = N;
	alese = 0;
	ncmin = 1 << 32 - 1;
	mnext = 0;
	ncmin = 1;
	while ( nci > 0 ) {

	  printf("caut %d\n", ncmin);
	  // caut gutui cu nc egal cu ncmin si aleg pe cele cu g max
	  maxg = 0;
	  im = -1;
	  for (i = 0; i < N; i++)
		if ( !vg[i].used && vg[i].g > maxg && (H - vg[i].h) / U + 1 == ncmin ) {
		  maxg = vg[i].g;
		  im = i;
		}
	  if ( im == -1 )
		break;
	  vg[im].used = 1;
	  alese++;
	  for (i = 0; i < N; i++)
		if ( !vg[i].used && vg[i].g > maxg && (H - vg[i].h) / U + 1 > ncmin &&  ncmax   <  (H - vg[i].h) / U + alese + 1 ) {
			printf("am pierdut %d\n", vg[i].g);
			vg[im].used = 0;
			ncmin++;
			alese--;
			break;
		}
	  if ( vg[im].used ) {
		printf("\tam ales %d \n", vg[im].g);
		sol += vg[im].g;
		
	  }
	  
	  nci--;
	}
*/
	sol = 0;
	for ( im = 1; im <= ncmax; im++ ) {
		maxg = vg[i].g;
		sg = 0;
		i = 0;
		nci = im;
		while ( i < N && nci <= ncmax ) {
				if ((H - vg[i].h) / U + 1 == nci && vg[i].g > maxg) {
					maxg = vg[i].g;
				} else {
					sg = sg + maxg;
					printf("aleg %d %d\n", vg[i].h, vg[i].g);
					maxg = vg[i].g;
					nci++;
				}
			i++;
		}
		//if ((H - vg[i].h) / U + 1 == nci )
		  sg = sg + maxg;
		if ( sg > sol)
			sol = sg;
		printf("\n");
	}
	
	printf("%d\n", sol);
	FILE *f = fopen("gutui.out", "wt");
	fprintf(f, "%d\n", sol);
	fclose(f);
	
	return 0;
}