Cod sursa(job #439955)

Utilizator rurryRuxandra Nistor rurry Data 11 aprilie 2010 20:58:10
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 1.31 kb
#include <stdio.h>
#include <stdlib.h>
typedef struct {
	unsigned int height;
	unsigned int weight;
} fruit;

int compare (const void * a, const void * b)
{
	return (((fruit *)b ) ->weight - ((fruit *)a ) ->weight);
}


int main(){
	unsigned int h, u;
	int n, i, j;
	fruit *x;
	
	//se citesc datele din fisier
	FILE *fin = fopen("gutui.in", "r");
	fscanf(fin, "%d", &n);
	fscanf(fin,"%u", &h);
	fscanf(fin, "%u", &u);
	
	x = (fruit *) malloc( n *sizeof(fruit));
	
	for(i = 0; i < n; i++){
		fscanf(fin, "%u %u", &(x[i].height), &(x[i].weight));
	}
	fclose(fin);
	qsort(x, n, sizeof(x), compare);

	int n_crt = n, aux;
	unsigned int greutate = 0;
	for(i = 0; i < n_crt; i++){
		if(x[i].height <= h) {
			greutate += x[i].weight;
			aux = 0;
			//printf("\n%u >", x[i].height);
			for(j = i + 1; j < n_crt;j++)
			{
				//printf(" %u", x[j].height);
				n_crt -=aux;
				x[j].height = x[j + aux].height;
				x[j].weight = x[j + aux].weight;
			//daca gutuia este poate fi culeasa la un mom superior de timp
				if((h - x[j].height)/u + 1 >= (h - x[i].height)/u + 1){
					//printf("mata %u < %u\n",x[i].height, x[j].height );
					x[j].height += u;
					if(x[j].height > h)
						aux++;
				}
			}
		}
	}
	FILE *fout = fopen("gutui.out", "w");
	fprintf(fout, "%u", greutate);
	fclose(fout);	
	//printf("greutate : >%d<", greutate);	
	return 0;
}