Cod sursa(job #437524)

Utilizator marina.cioceaMarina Ciocea marina.ciocea Data 9 aprilie 2010 20:44:33
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 2.62 kb
#include<stdio.h>
#include<stdlib.h>

typedef struct{
	unsigned int height, weight;			
} Gutuie;

int compareH (const void * a, const void * b)
{
    Gutuie *g1=(Gutuie *)a;
    Gutuie *g2=(Gutuie *)b;
    return (g1->height) - (g2->height);
}

int compareV (const void * a, const void * b)
{
    Gutuie *g1=(Gutuie *)a;
    Gutuie *g2=(Gutuie *)b;
    return (g2->weight) - (g1->weight);
}

int main()
{
	int  N=0, H=0, U=0, i, hHeight, hValue, max, sum=0, sumV=0, *level, start, current, j, k;
	Gutuie *gutui, *copy;
	

	FILE * in = fopen("gutui.in", "r");
	if(in==NULL)
		return;	

	fscanf(in, "%d", &N);
	fscanf(in, "%d", &H);
	fscanf(in, "%d", &U);
//	printf("%d %d %d\n",N, H, U);
	
	gutui=(Gutuie*)malloc(N*sizeof(Gutuie));
	copy=(Gutuie*)malloc(N*sizeof(Gutuie));
	level=(int *)malloc(N*sizeof(int));
	
	for(i=0; i<N; i++)
	{
		fscanf(in, "%d", &gutui[i].height);
        fscanf(in, "%d", &gutui[i].weight);
	//	printf("h: %d  w:  %d\n", gutui[i].height, gutui[i].weight);
	}
	printf("\n");
	fclose(in);
	
	qsort (gutui, N, sizeof(Gutuie), compareH);
	for(i=0; i<N; i++)
		level[i]=(H-gutui[i].height)/U + 1;

	//****************SORTARE DUPA GREUTATE[PE PORTIUNI]*******
	for(i=0; i<N; i++)
	{
		start=i;
		current=level[i];
		k=0;
		while(current==level[i])
		{
			copy[k++]=gutui[i];
			i++;
		}
		if(start==(i-1))
			i--;
		else
		{	
            qsort(copy, i-start, sizeof(Gutuie), compareV);
    		for(j=start; j<i; j++)
    			gutui[j]=copy[j-start];
        }
	}

/*    printf("acum:\n");
	for(i=0; i<N; i++)
	{
	//	level[i]=(H-gutui[i].height)/U + 1;
		printf("h: %d  w:  %d  Pn:  %d\n", gutui[i].height, gutui[i].weight, level[i]);
    }
*/
    
    for(i=0; i<N; i++)
	{
        if(level[i]!=0)
        {     
    		current=level[i];
    		level[i]=0;
    		sum+=gutui[i].weight;
    		i++;
    		while(current==level[i] && i<N)
    		{
    			level[i]--;
    			i++;
    		}
    		i--;
        }		
	}
//	printf("SUM:%d\n", sum);

	//******************************* SCRIERE IN FISIER*****************************
	FILE * out = fopen("gutui.out", "w");
	fprintf(out, "%d", sum);
	fclose(out);
	//*******************************************************************************
	
//	getch();
	free(gutui);
	return 0;
    

}


/* x-version

		if(zero(levels)==1)
			break;
		max=gutui[i].weight;
		index=i;
		start=i;
		current=level[i];
		i++;
		while(level[i]==current)
		{
			if(gutui[i].weight>max)
			{
				max=gutui[i].weight;
				index=i;
			}
			i++;
		}
		gutui[index].weight=-1;
		for(j=start; j<i; j++)
			level[j]--;
*/