Cod sursa(job #437731)

Utilizator catalin.cioponeaCatalin Cioponea catalin.cioponea Data 10 aprilie 2010 00:41:23
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 3 kb
#include <stdio.h>
#include <stdlib.h>


typedef struct copac{
	int inaltime;
	int greutate;
}gutui;

int compare (const void * a, const void * b){
	gutui *x, *y;
	x = (gutui*)a;
	y = (gutui*)b;
	return y->greutate - x->greutate;
}



int main(){
	FILE *f = fopen("gutui.in", "r");
	FILE *g = fopen("gutui.out", "w");
	
	int N; // N = numarul de gutui din pom
	fscanf(f, "%d", &N);
	int H; // H = inaltimea maxima la care poate ajunge Gigel
	fscanf(f, "%d", &H);
	int U; // U = cu cat se ridica crengile copacului
	fscanf(f, "%d", &U);
	
	int *inaltimi, *greutati;
	gutui *pom;
	pom = (gutui *) malloc ( N * sizeof(gutui));
	int i, j;
	for (i = 0; i < N; i++){
		fscanf(f, "%d", &pom[i].inaltime);
		fscanf(f, "%d", &pom[i].greutate);
	}
	qsort(pom, N, sizeof(gutui), compare); //aici fac sortarea descrescatoare dupa greutate
	
	//calculez momentul pentru fiecare gutuie
	int *moment = (int *) malloc ( N * sizeof(int));
	for ( i = 0; i < N; i++ ){
		moment[i] = ( H - pom[i].inaltime) / U ;
	//	printf("mom: %d greutate: %d inaltime %d\n", moment[i], pom[i].greutate, pom[i].inaltime);
	}
	//printf("\n");
	int valabil[N];
	for ( i = 0; i < N; i++ ){
		valabil[i] = 0;//initial toate momentele sunt accesabile
		printf("inalt: %d   gre: %d   mom: %d\n", pom[i].inaltime, pom[i].greutate, moment[i]);
	}
	//printf("\n");
	int greutateaCuleasa = 0;
	for ( i = 0; i < N; i++ ){
		//printf("intra a %d oara in primul for\n", i);
		if ( valabil[moment[i]] == 0 ){
			valabil[moment[i]] = 1;
			//printf("greutate: %d   valabil[%d] = %d\n", pom[i].greutate, i,valabil[moment[i]] );
			printf("in if adaug greutatea: %d de la %d  cu momentul: %d\n", pom[i].greutate, pom[i].inaltime, moment[i]);
			greutateaCuleasa += pom[i].greutate;
		}
		else{
			//printf("intra in else\n");
			//printf("           greutate: %d   valabil[%d] = %d\n", pom[i].greutate, i,valabil[moment[i]] );
			for ( j = moment[i]; j >= 0; j-- ){
				//printf("moment[%d] = %d\n", j, moment[j]);
				if ( valabil[j] == 0 ){
					valabil[j] = 1;
					printf("in else adaug greutatea: %d de la %d  cu momentul: %d\n", pom[i].greutate, pom[i].inaltime, moment[i]);
					greutateaCuleasa += pom[i].greutate;
					break;
				}
			}
		}
	}
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
/*	i = 0;
	while ( pom[i].inaltime + i * U < H && i < N ){
		printf("inaltime = %d  greutate: %d\n", pom[i].inaltime, pom[i]. greutate);
		for ( int j = i; j < N; j++ ){
			if ( pom[j].inaltime + i * U < H ){
				greutateaCuleasa += pom[i].greutate;
				printf("greutateaCuleasa: %d  inaltime: %d   greutate: %d\n", greutateaCuleasa, pom[j].inaltime, pom[j].greutate);
				i = j;
				break;
				//i = j;
			}
		}
		i++;
	}*/
//	printf("\n");
	printf("greutatea finala: %d\n", greutateaCuleasa);
//	printf("\n");
//	printf("%d %d %d\n", N, H, U);	
	//for ( i = 0; i < N; i++ )
		//printf("%d  %d\n", pom[i].inaltime, pom[i].greutate);
	
	fprintf(g, "%d", greutateaCuleasa);
	fclose(f);
	fclose(g);
	getchar();
	return 0;
}