Cod sursa(job #441467)

Utilizator IceyLiviu Grandl Icey Data 12 aprilie 2010 22:26:25
Problema Gutui Scor 60
Compilator c Status done
Runda teme_upb Marime 2.29 kb
#include<stdio.h>
#include<stdlib.h>

typedef struct gut{
	int inal, greut;
}gut;


	void afisare(gut *a, int n)
	{
		printf("\n");
		int i;
		for(i =0; i< n; i++)
			printf("%d Inaltime %d, Greutate %d\n", i, a[i].inal,a[i].greut); 
	}

	int compare(const void* x,const void* y)
	{
	    return (((gut*)x)->inal) <= (((gut*)y)->inal);
	}
	
	int h,u;
	
	int compare1(const void* x, const void* y)
	{
		if(((h-(((gut*)x)->inal))/u)!=((h-(((gut*)y)->inal))/u))
			if ((((gut*)x)->inal) < (((gut*)y)->inal))
						return 1;
			else
						return -1;
		else
			   return (((gut*)x)->greut) <= (((gut*)y)->greut);
			
	}	
	

	int minim(int *c,int n){
		int min = c[0];
		int i;
		for(i = 1; i <n; i++)
			if(c[i] < min)
				min = c[i];
		return min;

	}

	int main()
	{
	FILE *f, *fo;
	f = fopen("gutui.in", "r");
	fo = fopen("gutui.out", "w");
	int n, i, j;
	gut *a = NULL;

	fscanf(f, "%d", &n);
	fscanf(f, "%d", &h);
	fscanf(f, "%d", &u);

	a = (gut*)malloc(n * sizeof(gut));
	for(i = 0; i < n; i++)
	{
		fscanf(f, "%d", &a[i].inal);
		fscanf(f, "%d", &a[i].greut);
	}

	qsort(a, n, sizeof(gut), compare);//ordonare descresc dupa nivele, iar daca sunt pe acelasi nivel, dupa greutate

//	afisare(a,n);
			
	// nr cate nivele sunt folosite, si cate gutui sunt pe fiecare nivel, pentru a aloca vectori pt fiecare nivel
	//
	//h inaltimea maxima

	int *cos;
	cos = (int*)malloc(n*sizeof(int));
	for(i = 0; i <n; i++)
		cos[i] = 0;

	
	int min, nec =0,poz = 0;
//	int h1 = h, nr_niv = 0;
	
	while(a[nec].inal > h && nec<n) //daca nu pot fi culese, sar peste ele ca nu ma intereseaza
		nec++;
//	printf("\nSunt %d gutui care un pot fi culese din start\n", nec);
	int k = 0;

	for(i = nec; i <n; i++)
		if(a[i].inal <= h)
		{
			cos[k++] = a[i].greut;
			for(j = i; j <n;j++)
				a[j].inal+=u;
			
		}
		else
		{
			min = cos[0];
			for(j = 1; j < k; j++)
				if( cos[j] < min)
				{
					min = cos[j];
					poz = j;
				}
//			printf("\nMinimul este %d, pe pozitia %d iar gutuia %d\n",min,poz,a[i].greut); 
			if(a[i].greut > min)
				cos[poz] = a[i].greut;
//				int x;
//			for(x = 0; x < k ;x++)
//				printf("%d ",cos[x]);
//			printf("\n");

		}
	// printf("\n In cos am %d gutui \n",k);
	int s = 0;
	for(i =0; i<k; i++)
	{	
		s += cos[i];
	}

//	printf("Suma maxima este: %d \n",s);
	fprintf(fo, "%d",s);

free(a);
fclose(f);
fclose(fo);
return 0;
	
	}