Cod sursa(job #433633)

Utilizator TokPhobiaCosoi Andrei TokPhobia Data 3 aprilie 2010 23:28:33
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 2 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;
	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+1; j >= 2; 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;
			}
			heightmod += u;
		}
		//daca e la limita
		if (!added && gutui[maxpoz].h+heightmod == h && !pick[1]) {
			//printf("Am adaugat gutuia pe poz %d\n", j);
			pick[j] = 1;
			//for (k=1; k<=n; k++)
			//	printf("%d ", pick[k]);
			//printf("\n");
			heightmod += u;
			totalsum += gutui[maxpoz].g;
			heightmod += gutui[maxpoz].h;
			added = 1;
		}
		//printf("Suma partiala %d\n", totalsum);
		gutui[maxpoz].g = -1;
	}
	
	fprintf(fout, "%d\n", totalsum);
	
	fclose(fin);
	fclose(fout);
	
	return 0;
}