Cod sursa(job #437417)

Utilizator daniela.eneEne Daniela daniela.ene Data 9 aprilie 2010 18:11:11
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 2.5 kb
#include <stdio.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h> 
#define MAXX 100000

void swap(unsigned long int *x,unsigned long int *y)
{
   unsigned long int temp;
   temp = *x;
   *x = *y;
   *y = temp;
}





int main () {
	
	FILE *f,*g;
	f=fopen("gutui.in","r");
	g=fopen("gutui.out","w");
	//unsigned long 
	unsigned long int n,h,u; // n:numar de gutui h: inamtimea max u:cu cat se ridica crengile
	fscanf (f, "%lu %lu %lu",&n,&h,&u);
	char c[MAXX];
	fgets(c,MAXX,f); // sa ajung pe urm linie
	int i,j;
	//unsigned long
	unsigned long int hi[MAXX], ui[MAXX];//inaltimea si greutatea
	unsigned long int haux[MAXX], uaux[MAXX]; //cat a cules la un moment  + GREUTATEA pt fiecare gutuie culeasa
	unsigned long int gmax=0; // greutatea maxima
	
	for (i=0;i<n;i++) {
		fscanf (f, "%lu %lu",&hi[i],&ui[i]);	
		fgets(c,MAXX,f);// \n
	}
	/*printf ("\n hi \n");
	for (i=0;i<n;i++)
		printf ("%lu ",hi[i]);
		
	printf ("\n ui \n");
	for (i=0;i<n;i++)
		printf ("%lu ",ui[i]);
		*/
	//sortare vector
	for(i=0;i<(n-1);i++)
      		for(j=0;j<(n-(i+1));j++)
            		 if(hi[j] < hi[j+1]) {
                    		swap(&hi[j],&hi[j+1]);
				swap(&ui[j],&ui[j+1]);
			}
	/*printf ("\n hi \n");
	for (i=0;i<n;i++)
		printf ("%lu ",hi[i]);
		
	printf ("\n ui \n");
	for (i=0;i<n;i++)
		printf ("%lu ",ui[i]);
		
	*/	
	//deci asadar si prin urmare
	//acum iau fiecare elem din hi vad daca pot sa il adaug la structura
	//daca pot il adaug : daca nu p ot vad ce element as putea inlocui a i structura sa fie optima
	//in hi : inaltime ui : greutate ; h: cat am disponibil ; u : cat o sa scad
	//haux[MAXX], uaux[MAXX],gmaxi[MAXX]; e 
	int k = 0; //contor pt a numara cate elem voi avea in haux[MAXX], uaux[MAXX]; 
	for (i = 0; i < n;i ++ )
		if (hi[i] <= h) {
			haux[k] = hi[i];
			uaux[k] = ui[i];
			gmax +=ui[i]; //adaug la greutate
			//printf ("\ngmax %lu pentru hi la la%lu \n",gmax,hi[i]);
			h -=u ; //scad inaltimea
			k++; //cresc nr de elem
		}
		else {
		//aici e prob : ma uit in cele adaugate deja si vad pe care il pot inlocui
			for (j=0;j<k;j++)
				if (ui[i] > uaux[j]) {
					//printf (" %lu %lu %lu",gmax,ui[i],uaux[j]);
					
					gmax =gmax + ui[i] - uaux[j];
					haux[j] = hi[i];
					 
					uaux[j] = ui[i];
					
					//printf ("gmax %lu pentru hi %lu \n",gmax,hi[i]);
				}
		}
/*	printf ("\n haux \n");	
	for (i=0;i<k;i++)
		printf ("%lu ",haux[i]);
		
	printf ("\n uaux \n");
	for (i=0;i<k;i++)
		printf ("%lu ",uaux[i]);
	printf ("\ngreutate maxima la la la %lu \n" , gmax);	
		*/
	fprintf(g, "%lu",gmax);
		
		
	return 0;
}