Cod sursa(job #434855)

Utilizator andreea_0630Sandu Andreea andreea_0630 Data 6 aprilie 2010 17:34:31
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 1.91 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>


//structura care reprezinta o gutuie
typedef struct {
	long long int h;		//inaltimea gutuii
	long long int g;		//greutatea	gutuii
}Gutuie;

//functia de comparare pentru qsort 
int myfunction(const void *a, const void *b)
{
    Gutuie *ia = (Gutuie *)a;
    Gutuie *ib = (Gutuie *)b;
    return (ib->h - ia->h);			//facem o sortare descrescatoare
} 




int main(){
	long long int i,s = 0,k = 0;		//s = suma, k = pasul curent
	long long int aleasa = 0;			//ultima gutuie aleasa (greutatea acesteia)
	Gutuie gutui[100005];	//vectorul de structuri Gutuie
	long long int N,H,U;			//N-nr de gutui, H-inaltimea maxima la care ajunge Gigel
						//U-cu cat se ridica crengile copacului dupa culegerea unei gutui
	FILE *fin,*fout;
	fin = fopen("gutui.in","r");
	fout = fopen("gutui.out","w");
	
	fscanf(fin,"%lld %lld %lld",&N,&H,&U);	//citim din fisier N,H,U
	
	for (i = 0; i < N; i++)				//si fiecare gutuie
		fscanf(fin, "%lld %lld", &gutui[i].h, &gutui[i].g);
		
	qsort(gutui,N,sizeof(Gutuie),myfunction);		//sortam descrescator
	
	for (i = 0; i < N; i++){			//pentru fiecare gutuie in parte
			if (gutui[i].h + k*U <= H){		//daca Gigel poate sa ajunga la gutuie
			    aleasa = gutui[i].g;		//alegem gutuia (tinem minte greutatea ultimei gutui)
				k++;						//crestem pasul (nr de gutui gasite pana acum)
				s = s + gutui[i].g;			//crestem greutatea totala
			}
			else
				if (gutui[i].h + (k-1)*U <= H && gutui[i].g > aleasa){		//daca am ajuns la o gutuie pe care
				//am fi putut sa o introducem la pasul anterior, verificam daca greutatea sa e mai mare decat 
				//greutatea gutuii alese anterior
					s = s - aleasa;			//scadem greutatea gutuii anterioare
					aleasa = gutui[i].g;	//ultima gutuie aleasa devine cea curenta
					s = s + gutui[i].g;		//adunam greutatea la suma totala
				}
	}
	fprintf(fout,"%lld", s);
	
	fclose(fin);
	fclose(fout);
	return 0;
}