Cod sursa(job #439646)

Utilizator DetudaArthur Koestler Detuda Data 11 aprilie 2010 17:57:11
Problema Gutui Scor 20
Compilator c Status done
Runda teme_upb Marime 3.09 kb
#include <stdio.h>

	// nr gutui, inaltimea maxima, inaltarea, rezultatul final
	long n, hi, u, smax;
	// inantimea fiecarei gutui si greutatea
	long h[100001], w[100001], i, j, aux, nrs, found, k;
	long hmin, h1[100001], w1[100001], imax, max;

void rise()
{
	for(i=0; i<n; i++)
	h[i]+=u;
}

void update()
{
	// nu are sens sa pastram in vectorii h si w valorile pentru fructele care nu mai pot fi accesate (sunt prea sus)		
	j=0;
	for(i=0; i<n; i++)
	if(h[i]<=hi)
	{
		h1[j]=h[i];
		w1[j]=w[i];
		j++;
	}
	n=j;
	for(i=0; i<n; i++)
	{
		h[i]=h1[i];
		w[i]=w1[i];
	}
}


void swap(long *x, long *y)
{
   long auxi;
   auxi = *x;
   *x = *y;
   *y = auxi;
}

long pivot(long i, long j)
{
   return((i+j)/2);
}

void quicksort(long m, long n)
{
   long i, j, k, l;
   if( m < n)
   {
      k = pivot(m, n);
      swap(&h[m], &h[k]);
      swap(&w[m], &w[k]);
      l = w[m];
      i = m+1;
      j = n;
      while(i <= j)
      {
         while((i <= n) && (w[i] <= l))
                i++;
         while((j >= m) && (w[j] > l))
                j--;
         if( i < j)
         {
		swap(&h[i], &h[j]);
		swap(&w[i], &w[j]);
	 }
      }
      swap(&h[m], &h[j]);
      swap(&w[m], &w[j]);
      quicksort( m, j-1);
      quicksort( j+1, n);
   }
}


int main()
{
	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]);

	//sortam descrescator fructele, in functie de greutate
	//trebuie inlocuit cu quicksort, de exemplu
	quicksort(0, n-1);
	
	printf("Dupa quicksort, ordonate in functie de greutate: \n");
	for(i=0; i<n; i++)
	{
		h1[n-1-i]=h[i];
		w1[n-1-i]=w[i];
	}
	for(i=0; i<n; i++)
	{
		h[i]=h1[i];
		w[i]=w1[i];
		printf("fructul %ld are inaltimea %ld si greutatea %ld\n", i, h[i], w[i]);
	}
	

	smax=0;
	//trebuie la inceput sa elimin valorile prea inalte
	update();

	/*
	hmin=h[n-1];
//	printf("hmin este: %ld\n", hmin);
	nrs=(hi-hmin)/u+1;
	printf("numarul de sectoare este: %ld\n", nrs);
	*/

	while(n>0)
	{
		hmin=hi;
		for(i=0; i<n; i++)
		if(h[i]<hmin)
			hmin=h[i];
		nrs=(hi-hmin)/u+1;
		// printf("numarul de sectoare este: %ld\n", nrs);
		// ne intereseaza acum doar primele nrs fructe, in ordinea greutatii, la care ne vom referi ca "fructele grele"
		k=0, found=0;
		while (found==0) // cautam cel mai inalt fruct care face parte dintre aceste fructe grele
		{
			k++;
			for(i=0; i<nrs; i++)
			if(h[i]+k*u>hi && h[i]+(k-1)*u<=hi)
			{
				found=1;
				break;
			}
		} // k reprezinta stratul pe care am gasit un fruct din cele grele
		max=0, imax=-1;
		for(i=0; i<nrs; i++) // din fructele grele care se afla pe stratul cel mai de sus, il alegem pe cel mai greu
			if(h[i]+k*u>hi && h[i]+(k-1)*u<=hi &&w[i]>max)
			{
				imax=i;
				max=w[i];
			}
		smax+=max;
		for(i=imax+1; i<n; i++) // stergem fructul din vectorii inaltime si greutate
		{
			h[i-1]=h[i];
			w[i-1]=w[i];
		}
		n--;
		rise(); // toate fructele ramase se inalta
		update(); // nu ne mai intereseaza fructele inaccesibile
	}
			
	printf("%ld\n", smax);
	fprintf(g, "%ld", smax);
	
	fclose(f);
	fclose(g);
	return 0;
}