Cod sursa(job #439966)

Utilizator vitalie23vitalie vitalie23 Data 11 aprilie 2010 21:05:31
Problema Gutui Scor 20
Compilator c Status done
Runda teme_upb Marime 2.74 kb
#include <stdio.h>
#include <stdlib.h>


void swap (long *vec, long n, long poz)
{
	long aux;
	
	aux = vec[n - 1];
	vec[n - 1] = vec[poz];
	vec[poz] = aux;
}


void printVec (long *vec, long n)
{
	long i;
	
	for (i = 0; i < n; i++)
	{
		printf("%ld ", vec[i]);
	}
	printf("\n");
}


void quicksort (long *high, long *wheight, long left, long right)
{ 
    long i = left;
	long j = right;
	long aux;
    long x = wheight[left];
    do
    {    
        while (wheight[i] > x) i++; 
        while (wheight[j] < x) j--;
        if (i<=j)
        {
            aux = wheight[i]; wheight[i] = wheight[j]; wheight[j] = aux;
            aux = high[i]; high[i] = high[j]; high[j] = aux;
            i++; j--;
        }
    } while (i <= j);
    if (left < j) quicksort(high, wheight, left, j);
    if (i < right) quicksort(high, wheight, i, right);
}


long getLevel (long x, long h, long u, long nr)
{
	h -= u;
	while (x < h)
	{
		nr--;
		h -= u;
	}
	return nr;
}

int main ()
{
	long n, h, u;
	long *high, *wheight;
	FILE *fin, *fout;
	long i, nrLevel = 0, temp;
	long gmax = 0;
	long *aux;
	long level, nrGutui = 0;
	
	fin = fopen ("gutui.in", "r");
	if (fin == NULL)
	{
		printf("reading error!\n");
		exit(0);
	}
	fout = fopen ("gutui.out", "w");
	
	fscanf(fin, "%ld %ld %ld", &n, &h, &u);
	
	high = (long*)malloc (n * sizeof (long));
	wheight = (long*)malloc (n * sizeof (long));
	
	for (i = 0; i < n; i++)
	{
		fscanf(fin, "%ld %ld", &high[i], &wheight[i]);
	}
	quicksort (high, wheight, 0, n-1);
	
	temp = h;
// cate gutuie maxim pot culege
	while (temp > 0)
	{
		temp -= u;
		nrLevel++;
	}
	temp = nrLevel;
	aux = (long*)malloc (nrLevel * sizeof (long));
	for (i = 0; i < nrLevel; i++)
	{
		aux[i] = temp;
		temp--;
	}

/*	
i = 0;
	printf("%d\n", nrLevel);
	printVec (high, n);
	printVec (wheight, n);
	printVec (aux, nrLevel);
	level = getLevel (high[i], h, u, nrLevel - 1);
	printf("%ld\n", level);
*/
	i = 0;
	do
	{
	printf ("------------------------------------->>>>>>N = %ld I = %ld\n", n, i);
		printVec (high, n);
		printVec (wheight, n);
		printVec (aux, nrLevel);
		printf("GUTUIA VERIFICATA %ld %ld\n", high[i], wheight[i]);
		if (high[i] > h)
		{
			i++;
			continue;
		}
		level = getLevel (high[i], h, u, nrLevel - 1);
		printf("LEVEL %ld\n", level);
// culeg gutuia
		if (aux[level] > 0)
		{
			while (level >= 0)
			{
				aux[level]--;
				level--;
			}
			printf("Culeg gutuia\n");
			gmax += wheight[i];
			nrGutui++;
		}
		i++;
	}while (i < n && nrGutui < nrLevel);
	
	printf("%ld %ld\n", nrGutui, nrLevel);
	for (i = 0; i < n; i++)
	{
		if (high[i] == 0)
		{
			gmax += wheight[i];
		}
	}
	fprintf(fout, "%ld\n", gmax);

	return 0;
}