Cod sursa(job #435054)

Utilizator copotalex copot Data 6 aprilie 2010 20:42:05
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 3.58 kb
#include <stdio.h>
#include <stdlib.h>

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

gutuie vg[100000];
unsigned long N, H, U;

void citeste()
{
	FILE *f = fopen("gutui.in", "rt");
	int i;
	if ( f == NULL )
		return;
		
	fscanf(f, "%ld%ld%ld", &N, &H, &U);
	for (i = 0; i < N; i++)
		fscanf(f, "%ld%ld", &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;
}

int comp5(const void *s1, const void *s2)
{
	return ((gutuie*)s2)->g / (( H - ((gutuie*)s2)->h ) / U+1) - ((gutuie*)s1)->g / (( H - ((gutuie*)s1)->h ) / U+1);
	//return ((gutuie*)s2)->g / 2 ;//( H - ((gutuie*)s2)->h ) / U ;
	
		  // ((gutuie*)s1)->g / ( H - ((gutuie*)s1)->h ) / U;
}

int main(int argc, char **argv)
{
	unsigned long maxg, sol;
	unsigned long 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 %ld\n", ncmax);
	sol = 0;	
	for (i = 0; i < N; i++)
		printf("%ld %ld -> %ld\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;
	i = 0;
	sg = 0;
	for ( im = 1; im <= ncmax; im++ ) {
		maxg = 0;

		
		nci = im;

		while ( i < N && (H - vg[i].h) / U + 1 == nci ) {
		  if ( vg[i].g > maxg )
			maxg = vg[i].g;
		  i++;
		}
		if ( maxg == 0 )
		  continue;
		printf("aleg %ld la %ld\n", maxg, nci);
		
		sg = sg + maxg;

		printf("\n");
	}
	sol = sg;*/
	sol = vg[0].g;
	sg = vg[0].g / ((H - vg[0].h) / U+1);
	i = 1;
	printf("aleg %d\n", vg[0].g);
	while ( i < N ) {
	  if ( vg[i].g / ((H - vg[i].h) / U +1)< sg ) {
		sg = vg[i].g / ((H - vg[i].h) / U+1);
		sol = sol + vg[i].g;
		printf("aleg %d\n", vg[i].g);
	  }
	  i++;
	  
	}
	
	printf("%ld\n", sol);
	FILE *f = fopen("gutui.out", "wt");
	fprintf(f, "%ld\n", sol);
	fclose(f);
	
	return 0;
}