Cod sursa(job #441514)

Utilizator IceyLiviu Grandl Icey Data 12 aprilie 2010 22:45:55
Problema Gutui Scor 60
Compilator c Status done
Runda teme_upb Marime 2.39 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 inaltime

//	afisare(a,n);
			
	//
	//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;
	
	while(a[nec].inal > h && nec<n) //daca nu pot fi culese, sar peste ele ca nu ma intereseaza
		nec++;
	int k = 0;

	for(i = nec; i <n; i++)		//pornesc de la cate am accesibile, si iau fiecare gutuie	
		if(a[i].inal <= h)		// in caz ca aceasta gutuie e accesibila momentan, o adaug in cos, adica la vectorul de solutii cos
		{
			cos[k] = a[i].greut;
			k++;
			for(j = i+1; j <n;j++)		//cresc inaltimea tuturor gutuielor cu u(cele urmatoare)
				a[j].inal+=u;
			
		}
		else				//in caz ca gutuia este peste nivel..dar era insa accesbila odata
		{
			min = cos[0];
			for(j = 1; j < k; j++)		//calculez minimul dintre ce am cules pana acum
				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)		//in caz ca gutuia curenta e mai mare decat minimul dintre gutuile culese momentan..o inlocuiesc pe cea minima cu aceasta
				cos[poz] = a[i].greut;
		}
	int s = 0;
	for(i =0; i<k; i++)		//adun greutatile, si returnez in fisierul de out
	{	
		s += cos[i];
	}
	fprintf(fo, "%d",s);

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