Cod sursa(job #438975)

Utilizator boshcudanielDaniel Boscu boshcudaniel Data 11 aprilie 2010 10:33:59
Problema Gutui Scor 80
Compilator c Status done
Runda teme_upb Marime 1.54 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){
	
	struct gutui *X = (struct gutui *)x;
	struct gutui *Y = (struct gutui *)y;
	
	return (int)(Y->weight - X->weight);
}

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 vectorul de gutui dupa greutate
	
	qsort(tree, N, sizeof(struct gutui), cmpr_by_weight);
	
	basket = (gutui*)malloc(N*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;
		if (!basket[mom].weight){
			basket[mom].weight = tree[i].weight;
			basket[mom].height = tree[i].height;
		}
		else{
			for (j = mom; j >= 1; j--)
				if(!basket[j].weight){
					basket[j].weight = tree[i].weight;
					basket[j].height = tree[i].height;
					break;
				}
		}
	}
	
	for (i = 1; i <= N; i++)
		if (basket[i].weight)
			finalWeight += basket[i].weight;
	
	fprintf(f_out, "%d\n", finalWeight); 
	
	//for (i = 1; i <= N; i++)
		//fprintf(f_out, "%d %d %d\n", i, basket[i].height, basket[i].weight);
	
	fclose(f_in);
	fclose(f_out);
	return 0;
}