Cod sursa(job #439951)

Utilizator florin.dontuDontu Florin Gabriel florin.dontu Data 11 aprilie 2010 20:54:27
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 1.69 kb
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

// functie ce returneaza maximul dintr-un vector 

int max(int *vec, int n)
{
	int i, max = vec[0];
	for(i=1; i<n; i++)
		if(max <= vec[i])
			max = vec[i];
	return max;
}

// functie ce modifica vectorul astfel : inlocuieste primul maxim gasit cu 0 

void modifica(int *vec, int n)
{
	int i;
	for(i=0; i<n; i++)
		if(vec[i] == max(vec,n))
			{
			vec[i] = 0;
			break;
			}		
}

int h[249], g[249], i;
int n, hmax, u;

int main()
{
	FILE *in = fopen("gutui.in","r");
	FILE *out = fopen("gutui.out","w");
	
	fscanf(in,"%d ",&n);
	fscanf(in,"%d ",&hmax);
	fscanf(in,"%d\n",&u);

	//h = (int*)calloc(n,sizeof(int));
	//g = (int*)calloc(n,sizeof(int));
	for(i=0; i<n; i++)
		fscanf(in,"%d %d\n",&h[i],&g[i]);

	int k = 0, n_aux = n;
	int ng, *g_aux;			// vector auxiliar al greutatilor 
	int suma = 0;			// greutatea finala maxima
	int k1;
	
	while(n_aux)
		{
		ng = 0;
		k1 = 0;
		g_aux = (int*)calloc(n_aux,sizeof(int));
		for(i=0; i<n; i++)					// pentru fiecare inaltime diferita de 0 si incadrata in limitele multiplu de u
			if( (h[i] != 0) &&
				(h[i] >= hmax-(k+1)*u) && (h[i] < hmax-k*u) )	
				{
				g_aux[ng++] = g[i];			// introducem greutatile intr-un vector auxiliar
				h[i] = 0;				// facem 0 inaltimile parcurse
				n_aux--;				// scade numarul de gutui
				}
		k1 = k;		
		
		while( hmax-(k1+1)*u < hmax )			// cat timp nu s-a depasit inaltimea maxima 
			{
			suma += max(g_aux, ng);		// adunam la greutatea finala maximul din greutatile ramase in vectorul auxiliar 
			modifica(g_aux, ng);			// punem 0 in locul greutatii maxime curente
			
			k1--;
			}	
		k++;		
			
		free(g_aux);	
		}
	
	fprintf(out,"%d",suma);

	fclose(in);
	fclose(out);
	
	return 0;
}