Cod sursa(job #439238)

Utilizator boshcudanielDaniel Boscu boshcudaniel Data 11 aprilie 2010 14:34:18
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 1.91 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct gutui{
	int height;
	int weight;
} gutui;

int cmpr_by_weight (const void *x, const void *y){	//Comparator folosit de qsort
	
	struct gutui *X = (struct gutui *)x;
	struct gutui *Y = (struct gutui *)y;
	
	return (int)(Y->weight - X->weight);			//pozitiv daca y mai mare ca x
}

int main(){
	FILE *f_in, *f_out;
	int N, H, U;
	int i, j;
	int mom; //momentul la care cel tarziu poate fi culeasa o gutuie
	int finalWeight = 0;
	gutui *tree;
	gutui *basket;
	
	f_in = fopen("gutui.in", "r");
	f_out = fopen("gutui.out", "w");
	
	//Citire
	
	fscanf(f_in, "%d%d%d", &N, &H, &U);
	tree = (gutui*)malloc(N*sizeof(gutui));
	for (i = 0; i < N; i++){
		fscanf(f_in, "%d%d", &tree[i].height, &tree[i].weight);
	}
	
	//Sortam descrescator vectorul de gutui dupa greutate
	
	qsort(tree, N, sizeof(struct gutui), cmpr_by_weight);
	
	basket = (gutui*)malloc((N+1)*sizeof(gutui));
	
	for (i = 1; i <= N; i++){		//initializam cosul de gutui
		//basket[i].height = 0;
		basket[i].weight = 0;
	}
	
	for (i = 0; i < N; i++){
		mom = ( H - tree[i].height )/U + 1;		//formula pt a afla cand poate fi culeasa cel tarziu gutuia curenta(totodata si cea mai grea gutuie)
		if (!basket[mom].weight){				//daca in momentul respectiv nu e culeasa nicio gutuie o culegem pe aceasta 
			basket[mom].weight = tree[i].weight;
			//basket[mom].height = tree[i].height;
		}
		else{									//daca in momentul respectiv se culege alta gutuie cautam un moment anterior in care poate fi culeasa
			for (j = mom; j >= 1; j--)
				if(!basket[j].weight){			//daca nu exista gutuie culeasa
					basket[j].weight = tree[i].weight;	//o culegem
					//basket[j].height = tree[i].height;
					break;
				}
		}
	}
	
	for (i = 1; i <= N; i++)					//calculam masa totala din cos
		if (basket[i].weight)
			finalWeight += basket[i].weight;
	
	fprintf(f_out, "%d\n", finalWeight);		//afisam masa totala 
	
	fclose(f_in);
	fclose(f_out);
	return 0;
}