Cod sursa(job #433207)

Utilizator DetudaArthur Koestler Detuda Data 3 aprilie 2010 14:33:37
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 2.95 kb
#include <stdio.h>
#include <string.h>

void swap (long a, long b)
{
	long aux;
	aux=a;
	a=b;
	b=aux;
}

	// nr gutui, inaltimea maxima, inaltarea, rezultatul final
	long n, hi, u, smax=0;
	// inantimea fiecarei gutui si greutatea
	long h[100001], w[100001], i, j, aux, max, im;
	long hmin, nrs, k, s[100001], contor, x, y;

//imparte fructele in sectoare
void sectoare()
{
	for(k=1; k<=nrs; k++)
	for(i=0; i<n; i++)
	if(h[i]+k*u>hi && h[i]+(k-1)*u<=hi)
	{
		s[i]=k;
	}
}

//indicele fructului cu greutate maxima de pe sectorul k
long imax (long k)
{
	im=-100;
	max=-300;
	for(i=0; i<n; i++)
	if(w[i]>max && s[i]==k)
	{
		im=i;
		max=w[i];
	}
	return im;	
}

// verifica daca pe sectorul k sunt cel putin k elemente mai grele decat elementul x
int verifica(long x, long k)
{
	contor=0;
	for(i=0; i<n; i++)
	if(w[i]>w[x] && s[i]==k)
	contor++;
	if(contor>=k)
	return 1;
	else
	return 0;
}

//culege fructul cu indicele y, cu toate urmarile
void culege(long y)
{
	smax+=w[y];
	w[y]=-500;
	for(i=0; i<n; i++)
	{
		h[i]+=u;
		if(h[i]>hi)
		w[i]=-500;
	}
}
	

int main()
{
	int done;
	FILE *f=fopen("gutui.in", "r");
	FILE *g=fopen("gutui.out", "w");
	fscanf(f, "%ld %ld %ld", &n, &hi, &u);

	for(i=0; i<n; i++)
	fscanf(f, "%ld %ld", &h[i], &w[i]);
/*	for(i=0; i<n; i++)
	printf("fructul %ld are inaltimea %ld si greutatea %ld\n", i, h[i], w[i]);
*/
	//sortam descrescator fructele, in functie de inaltime
	//trebuie inlocuit cu quicksort, de exemplu
	for(i=0; i<n-1; i++)
	for(j=i+1; j<n; j++)
	if(h[i]<h[j])
	{
	//swap(h[i], h[j]);
	//swap(w[i], w[j]);
	aux=h[i];
	h[i]=h[j];
	h[j]=aux;
	aux=w[i];
	w[i]=w[j];
	w[j]=aux;
	}
	printf("Dupa quicksort: \n");
	for(i=0; i<n; i++)
	printf("fructul %ld are inaltimea %ld si greutatea %ld\n", i, h[i], w[i]);
	
	hmin=h[n-1];
	printf("hmin este: %ld\n", hmin);
//pana aici sigur e bine
	nrs=(hi-hmin)/u+1;
	printf("numarul de sectoare este: %ld\n", nrs);

	//the core shit
	done=0;
	//cat timp n-am terminat
	while(done==0)
	{
		//(re)impartim fructele in sectoare, in functie de inaltimile curente
		sectoare();
		//indicele elementului maxim din sectorul 1
		x=imax(1);
		//daca are valoarea -100 inseamna ca nu exista niciun element pe sectorul 1
		// in acest caz se culege maximul din intreaga multime
		if(x==-100)
		{
			max=-200;
			for(i=0; i<n; i++)
			if(w[i]>max)
			{
				im=i;
				max=w[i];
			}
			culege(im);
		}
		//altfel, daca sunt elemente pe sectorul 1
		else
		{
			k=nrs;
			//daca pe sectorul k sunt k elemente mai grele decat elementul x
			while(k>1)	
			{
				if(verifica(x, k)==1)
				break;
				k--;
			}
			//daca n-am gasit o astfel de situatie, culegem greutatea maxima de pe sectorul 1
			if(k==1)
			culege(x);
			//daca am gasit o astfel de situatie, culegem greutatea maxima de pe sectorul k
			else
			{
				y=imax(k);
				culege(y);
			}
		}
		//verificam daca am terminat, daca mai sunt fructe accesibile
		done=1;
		for(i=0; i<n; i++)
		if(h[i]<=hi)
		done=0;
	}
	fprintf(g, "%ld", smax);
	
	fclose(f);
	fclose(g);
	return 0;
}