Cod sursa(job #437081)

Utilizator bogdan.davidoaiaDavidoaia Bogdan bogdan.davidoaia Data 9 aprilie 2010 12:13:48
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 2.78 kb
// Davidoaia Bogdan-Mihai	323CA

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

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

// compara dupa inaltime (si greutate daca e1.h = e2.h) 2 gutui
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;
}

// interclasare a si b
// intoarce un vector nou
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;
}

// alegere cele mai grele gutui din prev si crt
// se aleg maxim level+1 gutui
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++)
		if(h < g[i].h)
			g[i].h = -1;
		else
			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);

	// distribuire pe nivele a gutuilor
	i = 0;
	while(g[i].h == -1)
		i++;
	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);
	
	long *choice = NULL;
	long nc = 0;
	for(l = 0 ; l < nlevel; l++) 
		choice = best(choice, &nc, t[l], nl[l], l);
		
	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;
}