Cod sursa(job #441090)

Utilizator vitalie23vitalie vitalie23 Data 12 aprilie 2010 19:15:18
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 3.09 kb
#include <stdio.h>
#include <stdlib.h>


// sortez vectorii cu quicksort
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);
}


// gasesc nivelul pe care se afla gutuia
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, i, temp;
	long *high, *wheight, *aux;
	FILE *fin, *fout;
	long nrLevel = 0;
	long gmax = 0;
	long level, tempNrLevel, nrGutui = 0;
	int zero = 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]);
	}
// sortez gutuile dupa greutate
	quicksort (high, wheight, 0, n-1);
	
	temp = h;
// cate gutuie maxim pot culege
	while (temp > 0)
	{
		temp -= u;
		nrLevel++;
	}
	temp = nrLevel;
	
// creez un vector auxiliar de lungime h/u
// pe care il initializez cu nr de gutuie pe care le pot culege de pe nivele
// Ex: de pe nivelul (0, h] pot culege nrLevel gutui
//		pe cand de pe (h-u, h] doar o singura gutuie
	aux = (long*)malloc (nrLevel * sizeof (long));
	for (i = 0; i < nrLevel; i++)
	{
		aux[i] = temp;
		temp--;
	}

	tempNrLevel = nrLevel;
	i = 0;
	do
	{
// verific daca initial exista vreo gutuie la o inaltime mai mare decat h
		if (high[i] > h)
		{
			i++;
			continue;
		}
// verific daca exista vreo gutuie la inaltimea 0
		if (high[i] == 0)
		{
			if (zero == 0)
			{
				zero++;
				tempNrLevel++;
			}
//			printf("Culeg gutuia\n");
			nrGutui++;
			gmax += wheight[i];
			i++;
			continue;
		}
// aflu pe ce nivel se afla gutuia pe care o culeg
// verific de la nivele cele mai mici spre cele mari
// Ex: (h-u, h] .. (0, h]
		level = getLevel (high[i], h, u, nrLevel - 1);
// culeg gutuia
// mai intai verific daca o pot culege
		if (aux[level] > 0)
		{
// daca culeg o gutuie
// scad nr de gutui pe care le pot culege de pe nivelele inferioare
			while (level >= 0)
			{
				aux[level]--;
// daca am cules toate gutuile de pe un nivel
// atunci nu mai pot culege nici o gutuie de pe nivelele superioare
				if (aux[level] == 0)
				{
					temp = level;
					while (temp < nrLevel)
					{
						aux[temp] = 0;
						temp++;
					}
				}
				level--;
			}
			gmax += wheight[i];
			nrGutui++;
		}
		i++;
	}while (i < n && nrGutui < tempNrLevel);
	
	fprintf(fout, "%ld\n", gmax);

	return 0;
}