Cod sursa(job #439048)

Utilizator vitalie23vitalie vitalie23 Data 11 aprilie 2010 12:17:56
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 2.89 kb
#include <stdio.h>
#include <stdlib.h>


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


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

// TODO si in dependenta de inaltime;
int findMax (int *wheigh, int *high, int n, int down, int up)
{
	int i;
	int max = 0;
	int poz = -1;
	
	for (i = 0; i < n; i++)
	{
//	printf("%d %d\n", high[i], low);
		if (high[i] > down && high[i] <= up)
		{
			if (wheigh[i] > max)
			{
				max = wheigh[i];
				poz = i;
			}
			if (wheigh[i] == max)
			{
				if (high[i] > high[poz])
				{
					poz = i;
				}
			}
		}
	}
	return poz;
}


int functionX (int *high, int *wheigh, int *n, int poz, int *h, int u, int *gmax)
{
	int i, temp;
	int nr = 0;
	int index, up;
	
	temp = (*h);
	up = (*h);
	while (temp > high[poz])
	{
		temp = temp - u;
		nr++;
	}
//	printf("NR == %d\n", nr);
//	(*h) = (*h) - (u * nr);// !!
	
//	printVec (wheigh, (*n));
//	printf("Culeg gutuia cu greutate maxima %d %d\n", high[poz], wheigh[poz]);
	(*gmax) += wheigh[poz];
	swap (high, (*n), poz);
	swap (wheigh, (*n), poz);
	(*n)--;
	nr--;
	(*h) -= u;

//	printVec (high, (*n));
//	printVec (wheigh, (*n));

	
	while (nr > 0)
	{
		index = findMax (wheigh, high, (*n), temp, up);
		if (index == -1)
		{
			break;
		}
//		printf("GMAX == %d INDEX == %d\n", (*gmax), index);
//		printf("Culeg %d %d\n", high[index], wheigh[index]);
		(*gmax) += wheigh[index];
//		printf("GMAX == %d\n", (*gmax));
		swap (high, (*n), index);
		swap (wheigh, (*n), index);
		(*n)--; nr--;
		(*h) -= u;
//		printVec (high, (*n));
//		printVec (wheigh, (*n));
	}
//	h = temp; // h = h - (u * nr);
//	printf ("%d %d %d %d\n", temp, nr, (*h), (*gmax));
}


int main ()
{
	int n, h, u;
	int *high, *wheigh;
	FILE *fin, *fout;
	int i, poz, nrCulegeri;
	int gmax = 0;
	
	fin = fopen ("gutui.in", "r");
	if (fin == NULL)
	{
		printf("reading error!\n");
		exit(0);
	}
	fout = fopen ("gutui.out", "w");
	
	fscanf(fin, "%d %d %d", &n, &h, &u);
	
	high = (int*)malloc (n * sizeof (int));
	wheigh = (int*)malloc (n * sizeof (int));
	
	for (i = 0; i < n; i++)
	{
		fscanf(fin, "%d %d", &high[i], &wheigh[i]);
	}
	
//	printVec (high, n);
//	printVec (wheigh, n);
	while (n >= 0)
	{
//		printf("Caut gutui\n");
//		printf("H = %d N = %d\n", h, n);
//		printVec (high, n);
//		printVec (wheigh, n);
		
		poz = findMax(wheigh, high, n, 0, h);
		if (poz == -1)
		{
			break;
		}
		nrCulegeri = functionX (high, wheigh, &n, poz, &h, u, &gmax);
//		printf ("%d ", high[poz]);
	}
//		printf ("%d %d\n", h, n);
//		printf("Am cules %dkg\n", gmax);
//		printf("Au ramas\n");
//		printVec (high, n);
//		printVec (wheigh, n);
	fprintf (fout, "%d\n", gmax);
	
	fclose (fin);
	fclose (fout);
	
	return 0;
}