Cod sursa(job #433641)

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

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

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, heightmod = 0, added = 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=0; i<=n; i++)
		pick[i] = 0;
	
	//gasim gutuia cu greutatea maxima de n ori
	for (i=1; i<=n; i++) {
		//initializam niste variabile
		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;
			}
		
		/*
		//afisez gutuile
		for (j=1; j<=n; j++)
			printf("(%d, %d) ", gutui[j].g, gutui[j].h);
		printf("\n");
		*/
		
		//printf("Incerc sa adaug (%d, %d) la lant\n", gutui[maxpoz].g, gutui[maxpoz].h);
		//fflush(stdout);
		
		//posibil sa nu incadreze bine o gutuie situata la inaltimea maxima (exact) !!!!
		//vedem daca putem pune gutuia maxima
		//printf("Incerc sa o pun de pe poz %d\n", h/u-(gutui[maxpoz].h)/u+1);
		added = 0;
		heightmod = 0;
		for (j=h/u-(gutui[maxpoz].h)/u + !((gutui[maxpoz].h)%u); j >= 1; j--) {
			//calculam heightmod-ul pentru aceasta gutuie
			if (!pick[j]) {
				//printf("Am adaugat gutuia pe poz %d\n", j);
				pick[j] = 1;
				//for (k=1; k<=n; k++)
				//	printf("%d ", pick[k]);
				//printf("\n");
				totalsum += gutui[maxpoz].g;
				heightmod += gutui[maxpoz].h;
				added = 1;
				break;
			}
		}
		//printf("Suma partiala %d\n", totalsum);
		gutui[maxpoz].g = -1;
	}
	
	//printf("%d\n", totalsum);
	fprintf(fout, "%d\n", totalsum);
	
	fclose(fin);
	fclose(fout);
	
	return 0;
}