Cod sursa(job #439980)

Utilizator vitalie23vitalie vitalie23 Data 11 aprilie 2010 21:12:52
Problema Gutui Scor 40
Compilator c Status done
Runda teme_upb Marime 2.82 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;
	}
//	printf("nr %ld\n", nr);
	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);

//	for (i = 0; i < nr; i++)
//	{

	return 0;
}