Cod sursa(job #433652)

Utilizator TokPhobiaCosoi Andrei TokPhobia Data 3 aprilie 2010 23:59:49
Problema Gutui Scor 20
Compilator c Status done
Runda teme_upb Marime 1.42 kb
#include <stdio.h>
#include <stdlib.h>

#define FILEIN "gutui.in"
#define FILEOUT "gutui.out"
#define DISPLAY 0

typedef struct gutuie {
	int g, h;
} gutuie;

int main() {
	
	FILE *fin = fopen(FILEIN, "r"), *fout = fopen(FILEOUT, "w");
	int n, h, u, i, j, pick[500], max, maxpoz, totalsum = 0, k;
	gutuie gutui[500];
	
	fscanf(fin, "%d %d %d", &n, &h, &u);
	
	for (i=1; i<=n; i++)
		fscanf(fin, "%d %d", &gutui[i].h, &gutui[i].g);
	
	for (i=1; i<=h/u + 1; i++)
		pick[i] = 0;
	
	//gasim gutuia cu greutatea maxima de n ori
	for (i=1; i<=n; i++) {
		
		max = -1;
		maxpoz = 0;
		
		//luam urmatoarea gutuie maxima
		for (j=1; j<=n; j++)
			if (max < gutui[j].g) {
				max = gutui[j].g;
				maxpoz = j;
			}
		
		if (DISPLAY) printf("Incerc sa adaug (%d, %d) la lant\n", gutui[maxpoz].g, gutui[maxpoz].h);
		
		//vedem daca putem pune gutuia maxima
		for (j=h/u-(gutui[maxpoz].h)/u + !((gutui[maxpoz].h)%u); j >= 1; j--) {
			//calculam heightmod-ul pentru aceasta gutuie
			if (!pick[j]) {
				
				if (DISPLAY) printf("Am adaugat gutuia pe poz %d\n", j);
				
				pick[j] = 1;
				
				if (DISPLAY) {
					for (k=1; k<=n; k++)
						printf("%d ", pick[k]);
					printf("\n");
				}
				
				totalsum += gutui[maxpoz].g;
				break;
				
			}
		}
		
		if (DISPLAY) printf("Suma partiala %d\n", totalsum);
		
		gutui[maxpoz].g = -1;
	}
	
	if (DISPLAY) printf("%d\n", totalsum);
	
	fprintf(fout, "%d\n", totalsum);
	
	fclose(fin);
	fclose(fout);
	
	return 0;
}