Cod sursa(job #438523)

Utilizator veraconstVeronica Constantinoaia veraconst Data 10 aprilie 2010 20:49:52
Problema Gutui Scor 80
Compilator c Status done
Runda teme_upb Marime 2.2 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct gut
{	
	long int iteratie;
	long int greutate;
} gutui;

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 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 pi, long int n,long int iter)
{
	long int i;
	for (i=pi;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;
	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 max_iter(gutui *a,long int n)
{
	long int i,max=a[0].iteratie;
	for (i=1;i<n;i++)
		if (a[i].iteratie>max)
			max=a[i].iteratie;
	return max;
}

int main()
{
	FILE *f=fopen ("gutui.in","r");
	FILE *g=fopen ("gutui.out","w");
	
	gutui *a;
	long int n,h,u,i,inaltime,greutate,nr=0;
	fscanf(f,"%ld %ld %ld",&n,&h,&u);
	a=(gutui*)malloc(n*sizeof(gutui));
	long int gmax;
	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_desc);

	long imax=max_iter(a,n);
	gmax=0;
	long int j=0;
	for (i=0;(i<n)&&(j<imax);i++)
	{
		if (a[i].iteratie>0)
		{
			gmax=gmax+a[i].greutate;
			j++;
			inalta(a,i+1,n,a[i].iteratie);
		}
	}	

	fprintf (g,"%ld\n",gmax);
	free(a);
	fclose(f);
	fclose(g);

	return 0;
}