Cod sursa(job #437554)

Utilizator marina.cioceaMarina Ciocea marina.ciocea Data 9 aprilie 2010 21:42:53
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 3.23 kb
#include<stdio.h>
#include<stdlib.h>

typedef struct{
	unsigned int height, weight;			
	unsigned int level;
} 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, start, current, j, k, index;
	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));
	
	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++)
	{
		gutui[i].level=(H-gutui[i].height)/U + 1;
	//	printf("h: %d  w:  %d  Pn:  %d\n", gutui[i].height, gutui[i].weight, gutui[i].level);
    }

    for(i=0; i<N; i++)
    {
		while( gutui[i].level==0 && i<N )
			i++;
		if(i==N)
            break;
		current=gutui[i].level;
		index=i;
		max=gutui[i].weight;
		while((gutui[i].level==current || gutui[i].level==0) && i<N)
		{
			if(gutui[i].level==0)
				i++;
			else
			{
				if(gutui[i].weight>max)
				{
					max=gutui[i].weight;
					index=i;
				}
				i++;
			}
		}
		gutui[index].level=0;
		//printf("index %d\n")
		sum+=max;
	}
	//printf("sum  %d\n", sum);






	//****************SORTARE DUPA GREUTATE[PE PORTIUNI]*******
/*	for(i=0; i<N; i++)
	{
		start=i;
		current=gutui[i].level;
		k=0;
		while(current==gutui[i].level)
		{
			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]--;
*/