Cod sursa(job #435807)

Utilizator bogdan.davidoaiaDavidoaia Bogdan bogdan.davidoaia Data 7 aprilie 2010 21:18:51
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 2.71 kb
// Davidoaia Bogdam-Mihai	323CA

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

struct gutuie { 
	long h;		// inaltimea gutuii
	long w; 	// greutatea gutuii
};


int comph(const void *e1, const void *e2) {
	struct gutuie *a = (struct gutuie *)e1;
	struct gutuie *b = (struct gutuie *)e2;
	
	if(a->h != b->h)
		return a->h - b->h;
	return b->w - a->w;
}



long* merge(long *a, long na, long *b, long nb) {
	long *ret = (long *) malloc( (na + nb) * sizeof(long) );
	long i = 0, j = 0, k = 0;
	while(i < na && j < nb)
		if(a[i] > b[j]) 
			ret[k++] = a[i++];
		else
			ret[k++] = b[j++];
	while(i < na)
		ret[k++] = a[i++];
	while(j < nb)
		ret[k++] = b[j++];
	return ret;
}

long* best(long *prev, long *nc, long *crt, long nl, long level) {
	long *ret;
	long i;
	if(crt == NULL) 
		// nivelul curent e null, ramane alegerea precedenta
		return prev;
	if(prev == NULL) {
		// primul nivel nenul, se intoarce acest nivel
		ret = (long *) malloc(nl * sizeof(long));
		for(i = 0; i < nl; i++)
			ret[i] = crt[i];
		*nc = nl;
		return ret;	
	}
	ret = merge(prev, *nc, crt, nl);
	if(*nc + nl < level + 1)
		*nc = *nc + nl;
	else
		*nc = level + 1;
	free(prev);
	return ret;
}

int main() {
	
	long n, u, h;
	long i, j, l, k;
	struct gutuie *g;
	
	FILE *in = fopen("gutui.in", "r");
	fscanf(in, "%ld%ld%ld", &n, &h, &u);
	g = (struct gutuie *) malloc(n * sizeof(struct gutuie));
	for( i = 0; i < n; i++) 
		fscanf(in, "%ld%ld", &(g[i].h), &(g[i].w) );
	fclose(in);
	
	for( i = 0; i < n; i++)
		g[i].h = ceil( (h - g[i].h) / u);

	qsort(g, n, sizeof(struct gutuie), comph);

	// nlevel = nr de nivele pe care sunt distribuite gutuile
	long nlevel = g[n-1].h + 1;
	// nl[i] = min (nr de gutui pe nivelul i , i+1), i = 0,nlevel-1   
	long *nl = (long *) calloc(sizeof(long), nlevel);
	// t -> greutatile gutuilor puse pe nivele
	long **t = (long **) calloc(sizeof(long), nlevel);

	i = 0;
	while(i < n) {
		l = g[i].h;
		j = 0;
		while( (g[i].h == l) && j <= l && i < n) {
			j++;
			i++;
		}
		nl[l] = j;
		t[l] = (long *) malloc (j * sizeof(long));
		for(k = 0; k < j; k++) 
			t[l][k] = g[i-j+k].w;

		while(g[i].h == l && i < n)
			i++;
	}
	
	free(g);
/*	
	for( i = 0; i < nlevel; i++ ){
		if(t[i])
			for(j = 0; j < nl[i]; j++)
				printf("%ld ",t[i][j]);
			else
				printf("null");
		printf("\n");
	}
*/
	long *choice = NULL;
	long nc = 0;
	for(l = 0 ; l < nlevel; l++) {
		choice = best(choice, &nc, t[l], nl[l], l); 
	/*	for(i = 0; i < nc; i++)
			printf("%ld ",choice[i]);
		printf("\n");
*/	}
	FILE *out = fopen("gutui.out", "w");
	long s = 0;
	for(i = 0; i < nc; i++)
		s += choice[i];
	fprintf(out, "%ld\n",s);
	fclose(out);
	
	if(choice != NULL)
		free(choice);
	free(nl);
	for(i = 0; i < nlevel; i++)
		if(t[i] != NULL)
			free(t[i]);
	free(t);
	
	return 0;
}