Cod sursa(job #436476)

Utilizator rurryRuxandra Nistor rurry Data 8 aprilie 2010 16:47:48
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 1.66 kb
//NISTOR RUXANDRA
//321 CA

#include <stdio.h>
#include <stdlib.h>
typedef struct {
	unsigned int height, weight;
} fruct;

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

int main()
{
	unsigned int h, u;
	fruct *gutuie;
	int n;
	
	//se citesc datele din fisier
	FILE *fin = fopen("gutui.in", "r");
	fscanf(fin, "%d", &n);
	fscanf(fin,"%d", &h);
	fscanf(fin, "%d", &u);
	gutuie = (fruct *) malloc (n * sizeof(fruct));
	int i;
	for(i = 0; i < n; i++)
		fscanf(fin, "%d %d", &gutuie[i].height, &gutuie[i].weight);
	fclose(fin);
	
	
	//afisare de verificare
	qsort(gutuie, n, sizeof(fruct), compare);
	/*
	printf("%d %d %d\n", n, h, u);
	for(i = 0; i< n ; i++)
		printf("%d %d\n",gutuie[i].height, gutuie[i].weight);
	*/	
	int no = 0;
	unsigned int maxw = 0;
	unsigned int greutate = 0;
	i = 0;
	//offset = 1;
	while(i < n )
	{
		if(gutuie[i].height + no * u <= h) 
		{
			//printf("e mai mic");
		//daca gutuia mai poate fi atinsa
			if(gutuie[i].height + (no + 1) * u > h)
			{
				//printf("e intre");
			//daca gutuia tre luata la pasul asta
				if(maxw < gutuie[i].weight)
				{
					//printf("%d", gutuie[i].weight);
					maxw = gutuie[i].weight;
				}
				i++;
			}
			else 
			{
				//printf("aiiiici");
			//daca s-a ajuns la o gutuie care nu mai poate fi luata la pasul asta
				if(maxw > 0)
				//daca s-au gasit gutui care sa dispara la pasul curent
				{
					//offset = 1;
					greutate += maxw;
					maxw = 0;
					no++;
				}
				else
				{
					//while
				}
			}
		}
	}
	greutate += maxw;
	FILE *fout = fopen("gutui.out", "w");
	fprintf(fout, "%d", greutate);
	fclose(fout);
	//printf(">>>>>%d", greutate);	
	return 0;
}