Cod sursa(job #443210)

Utilizator aandreyAlbu Andrei aandrey Data 16 aprilie 2010 14:17:19
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 2.05 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int *greu;
int *high;
int *time;
int *best;
int n,U,H;

void exchange(int a, int b)
{
	int j;
	j=time[a];
	time[a]=time[b];
	time[b]=j;
	j=greu[a];
	greu[a]=greu[b];
	greu[b]=j;
}

void quickSort (int lo, int hi)
{
    int i=lo, j=hi, h;
    int x=time[(lo+hi)/2];

    while (i<=j)
    {    
        while (time[i]<x) 
        	i++; 
        while (time[j]>x) 
        	j--;
        if (i<=j)
        	{
        	exchange(i,j);
              	i++; 
            	j--;
        	}
    	}
    if (lo<j) quickSort(lo, j);
    if (i<hi) quickSort(i, hi);
}

void testQuickSort()
{
	int i;
	quickSort(0,n-1);
	for(i=0;i<n;i++)
        	printf("%d ",time[i]);

}

int getmin(int k)
{
	int min,i;
	min = k;
	for (i=k; i>=0; i--){
		if (best[min]>best[i])
			min=i;
	}
	return min;
}
void printVec(int *a)
{
	int i;
	for (i=0; i < n; i++)
		printf("%d ",a[i]);
	puts("");
}
int main()
{
	FILE *fp;
	fp=fopen("gutui.in","r");
	int i;
	
	fscanf(fp,"%d %d %d", &n, &H, &U);
	greu = (int *) calloc (n,sizeof(int));
	high = (int *) calloc (n,sizeof(int));	
	time = (int *) calloc (n,sizeof(int));		
	for (i=0; i<n; i++)
		{
		fscanf(fp,"%d %d", &high[i], &greu[i]);
		greu[i] = greu[i];
		high[i] = high[i];
		}
	for (i=0; i<n; i++)
		time[i]= (H-high[i])/U;
		
/*	printf("\nAFISARE GREUTATI\n");
	for (i=0; i<n; i++)
		printf("%d\n",greu[i]);
*/		
	quickSort(0,n-1);
	
		
	close(fp);
	best = (int *) calloc(n,sizeof(int));
	int pos;
	for (i=0; i<n; i++)
		{
		pos = getmin(time[i]);
	//	printf("pos=%d\n", pos);
		if (best[pos] < greu[i])
			best[pos] = greu[i];
	//	printf("i=%d\n",i);
		//printVec(best);
		}
	//printf("\nAFISARE TIMPI\n");
		
	/*for (i=0; i<n; i++)
		printf("%d ", time[i]);
	printf("\n");
	
	//printf("\n AFISARE TIMPI SI GREUTATI ORDONATI\n");
	/*for (i=0; i<n; i++)
		{
		printf("G:%d T:%d ",greu[i], time[i]);
		printf("\n");
		}
	
	//printf("\nAFISARE vector best\n");
	//printVec(best);
	*/
	fp=fopen("gutui.out","w");
	int sum;
	sum=0;
	for (i=0; i<n; i++)
		sum+=best[i];
	fprintf(fp,"%d",sum);
	fclose(fp);
	return 0;

	
}