Cod sursa(job #439147)

Utilizator thoradinMarius Latu thoradin Data 11 aprilie 2010 13:29:40
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 1.76 kb
#include <stdio.h>
#include <stdlib.h>

#define infile "gutui.in"
#define outfile "gutui.out"

int NMAX = 100000;
int N, H, U;

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

int compare_fruit(const void* A, const void* B)
{
	const fruit *a = A;
	const fruit *b = B;
	
	
	if (a->height < b->height)
		return -1;
	if (a->height > b->height)
		return 1;
	if (a->weight < b->weight)
		return -1;
	if (a->weight > b->weight)
		return 1;
	
	return 0;
}

int sum(fruit *fr)
{
	int i, s = 0;
	for (i = 0; i < N; i++)
		s += fr[i].weight;
		
	return s;
}

int solve(fruit* fr)
{
	if (U == 0)
		return sum(fr);
		
	int i;
	int current_height = 0, current_weight = 0;
	
	qsort(fr, N, sizeof(fruit), compare_fruit);
	
	for (i = N-1; i >= 0; i--)
	{
		if ((current_height + U) > H)
			break;
		if ((fr[i].height + current_height) <= H)
		{
			printf("Current weight: %d, Current height: %d\n", current_weight, current_height);
			printf("h: %d w:%d \n\n", fr[i].height, fr[i].weight);
			current_weight += fr[i].weight;
			current_height += U;
		}		
	}
	
	return current_weight;
}


int main()
{
	FILE *fin, *fout;
	
	/* Try opening files */
	if (!(fin = fopen(infile, "r"))) 
	{
		fprintf(stderr, "Could not open input file.\n");
		return -1;
	}
	if (!(fout = fopen(outfile, "w"))) 
	{
		fprintf(stderr, "Could not open output file.\n");
		return -1;
	}

	int i, weight;
	
	fscanf(fin, "%d %d %d", &N, &H, &U);
	if (N>NMAX)
	{
		fprintf(stderr, "Count size out of bounds.\n");
		return 1;
	}
	
	fruit* quinces;
	quinces = (fruit*) malloc(N*sizeof(fruit));
	
	for (i = 0; i < N; i++)
		fscanf(fin, "%d %d", &quinces[i].height, &quinces[i].weight);

	weight = solve(quinces);
	
	fprintf(fout, "%d\n", weight);
	
	/* Close files and free memory */
	free(quinces);
	
	fclose(fin);
	fclose(fout);
	
	return 0;
}