Cod sursa(job #436848)

Utilizator GrrreenVoinea Maria Anemona Grrreen Data 9 aprilie 2010 00:06:21
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 1.86 kb
//Voinea Maria Anemona 321CA
//--------Tema 1 PA---------

#include <stdio.h>
#include <stdlib.h>

int main()
{
	FILE *in, *out;
	int i, j, c, N, H, U, *h, *g, G=0, gutui=0, etape=0;
	char s[50];
	in = fopen("gutui.in", "r");
	out = fopen("gutui.out", "w");
	
	fgets(s, 50, in);
	sscanf(s, "%d%d%d", &N, &H, &U);
	//printf("%d %d %d\n", N, H, U);
	
	h = (int*)malloc(N*sizeof(int));
	g = (int*)malloc(N*sizeof(int));

	for(i=0; i<N; i++)
	{
		fgets(s, 50, in);
		sscanf(s, "%d%d", h+i, g+i);
	}
	fclose(in);
	
	//Calculul numarului maxim de gutui culese (numarul de etape ale culesului)
	for(i=0; i<N; i++)
	{
			if( H-h[i] > 0 && (H-h[i]) / U + 1 > etape )
				etape = (H-h[i]) / U + 1;
	}
	//printf("Etape: %d\n", etape);
	if(!etape)
	{
		fprintf(out, "Greutatea maxima: 0\n"); //nu se poate culege nimic
		return 0;
	}
	
	//Sortare dupa greutate
	for(i=0; i<N-1; i++)
		for(j=i+1; j<N; j++)
			if(g[i] < g[j])
			{
				c = g[i];
				g[i] = g[j];
				g[j] = c;
				c = h[i];
				h[i] = h[j];
				h[j] = c;	
			}
	
	int hi, hc;
	while(gutui < etape)
	{
		c = -1;
		hc = gutui;
		for (i=0; i<N; i++)
		{
			hi = (H-h[i]) / U; //etapa maxima la care se poate culege gutuia i
			//Daca nu a fost culeasa gutuia
				//si etapa maxima de culegere a ei e mai mica decat etapa curenta
			if(g[i] > 0 && hi >= gutui)
			{
				//Daca nu a fost aleasa inca o gutuie
					//sau etapa maxima a celei curente e mai mica decat a celei alese
				if(c==-1 || hi < hc)
				{
					c = i; 		//se alege gutuia curenta
					hc = hi; 	//se actualizeaza etapa maxima aleasa
				}
			}
		}
		if(c==-1) //daca nu s-au ales gutui se continua
		{
			gutui++;
			continue;
		}
		//printf("Culeasa cea de greutate %d\n", g[c]);
		G += g[c];
		g[c] = -1;
		gutui++;
	}
	//Afisare de control
	/*
	for(i=0; i<N; i++)
	{
		printf("%d %d\n", h[i], g[i]);
	}*/
	
	fprintf(out, "Greutatea maxima: %d\n", G);
	fclose(out);
	
	return 0;
}