Cod sursa(job #435091)

Utilizator veraconstVeronica Constantinoaia veraconst Data 6 aprilie 2010 21:44:17
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 1.63 kb
#include <stdio.h>
#include <stdlib.h>

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

int compare_desc (const void * a, const void * b)
{
    return ( *(int*)b - *(int*)a );
}
int compare_cresc (const void * a, const void * b)
{
    return ( *(int*)a - *(int*)b );
}

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

void inalta (gutui *a, long int pozi,long int pozf,long int c)
{
	long int i;
	for (i=pozi;i<pozf;i++)
		a[i].inaltime=a[i].inaltime+c;
	
}
void swap(gutui *x,gutui *y)
{
   gutui aux;
   aux = *x;
   *x = *y;
   *y = aux;
}

int main()
{
	FILE *f=fopen ("gutui.in","r");
	FILE *g=fopen ("gutui.out","w");
	
	gutui *a;
	long int n,h,u,i;
	fscanf(f,"%ld %ld %ld",&n,&h,&u);
	a=(gutui*)malloc(n*sizeof(gutui));
	for (i=0;i<n;i++)
	{
		fscanf(f,"%ld %ld",&a[i].inaltime,&a[i].greutate);
		a[i].iteratie=iteratii(h-a[i].inaltime,u);
	}
	qsort(a,n,sizeof(gutui),compare_cresc);
	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;
			}
	}
	
	i=0;
	long int gmax=0;
	while (i<n)
	{
		if (a[i].inaltime<=h)
		{
			gmax=gmax+a[i].greutate;
		        inalta(a,i+1,n,u);
		//	for (j=i+1;j<n;j++)
		  //        printf("%ld %ld\n",a[j].inaltime,a[j].greutate);
		}
		//printf("------------------------------\n");
		i++;
	}	
	fprintf (g,"%ld\n",gmax);
	//for (i=0;i<n;i++)
	//	printf("%ld %ld %ld\n",a[i].iteratie,a[i].inaltime,a[i].greutate);
	
	

	free(a);
	fclose(f);
	fclose(g);

	return 0;
}