Cod sursa(job #443650)

Utilizator mihai.dobreDobre Mihai mihai.dobre Data 17 aprilie 2010 19:56:01
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 3.46 kb
#include <stdio.h>
#include <stdlib.h>

#define N_MAX 100000

void Afis(int gutui[2][N_MAX],int n)
{
	int i=0;
	for (;i<n;i++)
	printf("%i:%i\n",gutui[0][i],gutui[1][i]);
}

void swap(int *x,int *y,int *z,int *q)
{
   int temp;
   temp = *x;
   *x = *y;
   *y = temp;
   temp = *z;
   *z = *q;
   *q = temp;
}
 
int choose_pivot(int i,int j )
{
   return((i+j) /2);
}
 
void quicksort(int list[2][N_MAX],int m,int n,int crit)
{
   int key,i,j,k;
   if( m < n)
   {
		k = choose_pivot(m,n);
		swap(&list[1][m],&list[1][k],&list[0][m],&list[0][k]);
		key = list[crit][m];
		i = m+1;
		j = n;
		while(i <= j)
		{
			while((i <= n) && (list[crit][i] <= key))
				i++;
			while((j >= m) && (list[crit][j] > key))
				j--;
			if( i < j)
				swap(&list[0][i],&list[0][j],&list[1][i],&list[1][j]);
		}
		// swap two elements
		swap(&list[0][m],&list[0][j],&list[1][m],&list[1][j]);
		// recursively sort the lesser list
		quicksort(list,m,j-1,crit);
		quicksort(list,j+1,n,crit);
	}
}
void printlist(int list[2][N_MAX],int n)
{
	int i;
	for(i=0;i<n;i++)
	printf("%d:%d\n",list[0][i],list[1][i]);
	printf("\n");
} 

void FindMax(int list[2][N_MAX],int n,int b,int *x)
{
	int max=list[1][n-1];
	int i;
	
	*x=n-1;
	*(x+1)=list[0][n-1];
	for(i=n-2;i>=b;i--)
		if(max<=list[1][i])
		{
			max=list[1][i];
			*x=i;
			*(x+1)=list[0][i];
		}
}

void FindHMax(int list[2][N_MAX],int n,int b,int *x)
{
	*x=n-1;
	int i;
	for(i=n-2;i>=b;i--)
		if(list[0][*x]<=list[0][i])
			*x=i;
}

int Accesibile(int pozMax,int hMax,int u)
{
	return hMax/u-pozMax/u;
}

void Inc(int list[2][N_MAX],int n,int u)
{
	int i=0;
	for (;i<n;i++)
		list[0][i]+=u;
}

void Remove(int list[2][N_MAX],int n,int poz)
{
	int i;
	for(i=poz;i<n-1;i++)
		{
			list[0][i]=list[0][i+1];
			list[1][i]=list[1][i+1];
		}
}

int Suma(int list[2][N_MAX],int n,int h,int u)
{
	int pozMax[2];
    int s=0;
	FindMax(list,n,0,pozMax);
	//printf("%i?|?%i\n",pozMax[0],pozMax[1]);
	int acces=Accesibile(pozMax[1],h,u);
	//printf("ACCESIBILE: %i\n",acces);
	int i=0;
	if (pozMax[0]!=n-1)
		{
			quicksort(list,pozMax[0],n-1,1);
			//printlist(list,n);
			
			//printf("urmeaza WHILE\n");
			while(i<acces)
			{	
				//printlist(list,n);
				s=s+list[1][n-1-i];
				i++;
			}
			n=n-acces;
			for(i=0;i<acces;i++)
				Inc(list,n,u);
			int j;
			for(j=0;j<n;j++)
						if(list[0][j]>h)
						{
							//printf("**a scos %i||%i **\n\n",list[0][j],list[1][j]);
							Remove(list,n,j);
							j--;
							n-=1;
						
						}
			//printlist(list,n);
		}
	else 
		{
		s=list[1][pozMax[0]];
		Inc(list,n,u);
		int j;
			for(j=0;j<n;j++)
						if(list[0][j]>h)
						{
							//printf("**a scos %i||%i **\n\n",list[0][j],list[1][j]);
							Remove(list,n,j);
							j--;
							n-=1;
						}
		}
		
		//printf("$$SUMA CURENTA %i $$\n\n",s);
		if(n>0)
			return s+Suma(list,n,h,u);
		return s;
}

int main()
{
	FILE *f;
	int n,h,u,i,x,y;
	f=fopen("gutui.in","r");
	fscanf(f,"%i %i %i",&n,&h,&u);
	//printf("%i %i %i\n",n,h,u);
	int gutui[2][N_MAX];
	for(i=0;i<n;i++)
	{
		fscanf(f,"%i %i",&x,&y);
		gutui[0][i]=x;
		gutui[1][i]=y;
    }
	close(f);
	//Afis(gutui,n);
	//printf("\n");
	quicksort(gutui,0,n-1,0);
	//printlist(gutui,n);
	//printf("\n");

	//int pozMax[2];
	
	//printf("\n");
	//printf("\n");
	x=Suma(gutui,n,h,u);
	FILE *g;
	g=fopen("fis.out","w");
	fprintf(g,"suma: %i",x);
	close(g);
	return 0;
}