Cod sursa(job #437486)

Utilizator veraconstVeronica Constantinoaia veraconst Data 9 aprilie 2010 19:55:06
Problema Gutui Scor 60
Compilator c Status done
Runda teme_upb Marime 3.74 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct gut
{	
	long int iteratie;
	//long int inaltime;
	long int greutate;
	//long int prioritate;
} gutui;

typedef struct p
{	
	long int iteratie;
	//long int inaltime;
	long int greutate;
	long int prioritate;
} prior;


int compare_desc (const void * a, const void * b)
{
    gutui *g1 = (gutui *)a;
    gutui *g2 = (gutui *)b;
    return ( g2->greutate - g1->greutate );
}
int compare_cresc (const void * a, const void * b)
{
    return ( *(long int*)a - *(long int*)b );
}
int compare_prior (const void * a, const void * b)
{
    prior *g1 = (prior *)a;
    prior *g2 = (prior *)b;
    return ( g2->prioritate - g1->prioritate );
}

int iteratii(long int a,long int b)
{
	ldiv_t result;
	result = ldiv(a,b);
	//if (result.rem==0) return result.quot+1;
	return result.quot+1;
}

void inalta (gutui *a, long int n,long int iter)
{
	long int i;
	for (i=0;i<n;i++)
		if (a[i].iteratie>=iter)
			a[i].iteratie--;
	
}
void swap(gutui *x,gutui *y)
{
   gutui aux;
   aux = *x;
   *x = *y;
   *y = aux;
}

long int numar_apar(gutui *a,long int x,long int pi,long int n)
{
	long int nr=0;
	long int i=pi;
	//int gasit=1;
	while (i<n)
	{
		if (x!=a[i].iteratie)
			break;
			
		i++;
		nr++;

	}
	return nr;
}

void copiere (gutui *s,gutui *d,long int pi,long int nr,long int *nd)
{
	long int i;
	for (i=pi;i<pi+nr;i++)
	{
		d[*nd]=s[i];
		*nd=*nd+1;
	}	
}

void creare_aux (gutui *s,gutui *d,long int n,long int *naux)
{
	long int i=0;
	long int nr;
	while (i<n)
	{
		nr=numar_apar(s,s[i].iteratie,i,n);
		if (nr<=s[i].iteratie)
		{
			copiere(s,d,i,nr,naux);
		
		}		
		else 
		{
			copiere(s,d,i,s[i].iteratie,naux);
		
		}
		i=i+nr;
	}
}

long int suma(gutui *a,long int pi,long int n, long int ne)
{
	long int i,s=0,k=0;
	//printf ("-----------------------\n");
	//printf ("%ld: ",pi);
	for (i=pi;((i<n)&&(k<ne));i++)
		if (a[i].iteratie>k)
		{			
			s=s+a[i].greutate;
			//printf (" %ld ",a[i].greutate);
			k++;
		}
	//printf ("\n");
	return s;
}

long int min_iter (gutui *a,long int n)
{
	long int min=a[0].iteratie;
	long int i;
	for (i=0;i<n;i++)
		if ((a[i].iteratie!=0)&&(a[i].iteratie<min))
			min=a[i].iteratie;

	return min;
}
long int suma_elem(gutui *a,long int n)
{
	long int i,s=0;
	for (i=0;i<n;i++)
		s=s+a[i].greutate;
return s;
} 
long int pozitie(prior x,gutui *a,long int n)
{
	long int i,poz;
	for (i=0;i<n;i++)
		if ((a[i].iteratie==x.iteratie)&&(a[i].greutate==x.greutate))
		{	poz=i;
			break;
		}
return poz;
}
int main()
{
	FILE *f=fopen ("gutui.in","r");
	FILE *g=fopen ("gutui.out","w");
	
	gutui *a,*aux;
	long int n,h,u,i,inaltime,greutate,j,k,max;
	fscanf(f,"%ld %ld %ld",&n,&h,&u);
	a=(gutui*)malloc(n*sizeof(gutui));
	aux=(gutui*)malloc(n*sizeof(gutui));
	long int naux=0;
	long int gmax;
	long int nr=0;
	prior *b;
	for (i=0;i<n;i++)
	{
		fscanf(f,"%ld %ld",&inaltime,&greutate);
		if (inaltime<h)
		{	
			a[nr].greutate=greutate;			
			a[nr].iteratie=iteratii(h-inaltime,u);
			nr++;
		}
	}
	n=nr;
	
	qsort(a,n,sizeof(gutui),compare_cresc);

	/*for (i=0;i<n;i++)
		printf("+%ld %ld\n",a[i].iteratie,a[i].greutate);*/
	
	
	/*i=0;
	while (i<n-1)
	{
		nr=1;
		j=i;
		while (j<n-1)
		{
			if (a[j].iteratie==a[j+1].iteratie)
				nr++;
			j++;
		}
		if (nr>1)
			qsort(a+(j-nr-2),nr-1,sizeof(gutui),compare_desc);	
		i=i+nr-1;
	}*/
	int sortat=1;
	while (sortat)
	{
		sortat=0;
		for (i=0;i<n-1;i++)
			if ((a[i].iteratie==a[i+1].iteratie)&&(a[i].greutate<a[i+1].greutate))
			{	
				swap(&a[i],&a[i+1]);
				sortat=1;
			}
	}
	
	

	creare_aux (a,aux,n,&naux);
	qsort(aux,naux,sizeof(gutui),compare_desc);
	
	gmax=0;
	for (i=0;i<naux;i++)
	{
		if (aux[i].iteratie>0)
		{
			gmax=gmax+aux[i].greutate;
			inalta(aux,n,aux[i].iteratie);
		}
	}	
	fprintf (g,"%ld\n",gmax);
	free(aux);
	free(a);
	fclose(f);
	fclose(g);

	return 0;
}