Cod sursa(job #439983)

Utilizator dorinpislaruPislaru Dorin dorinpislaru Data 11 aprilie 2010 21:13:53
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 2.78 kb
#include<stdio.h>
#include<stdlib.h>

//definesc o structura ce contine greutatea , inaltimea si nivelul la care se afla fiecare gutuie
typedef struct
{
    int g;
	 int h;
	 int nv;
}fruct;

//functie auxiliara pe care o folosesc in functia de sortare "qsort" pentru a ordona un vector de structuri de tip "fruct"
int fsort(const void* a,const void* b)
{
	 fruct* fr1=(fruct*)a;
	 fruct* fr2=(fruct*)b;
	 //daca 2 gutui au aceiasi greutate , le sortez crescator , dupa inaltime
	 if(fr1->g == fr2->g) return fr1->h - fr2->h;
	 //altfel le sortez dupa greutate
	 return fr2->g - fr1->g;
}

//functia principala
int main()
{
	 
	 int n,H,u;// "n"-nr de gutui , "H"-inaltimea maxima ,"u" -distanta cu care se ridica arborele 
	 int i,j;
	 int hmin=100000;//variabila in care retin inaltimea la care se afla cea mai de jos gutuie
	 int max=0;//variabila in care retin greutatea gutuilor culese
	 
	 //deshid fisierul pentru citirea datelor
	 FILE *f=fopen("gutui.in","r");
	 fscanf(f ,"%d" ,&n);
	 fscanf(f ,"%d" ,&H);
	 fscanf(f ,"%d" ,&u);
	 
	 //declar un vector de structuri de tip "fruct"
	 fruct a[n];
	 //in variabila "nrnv" retin numarul de nivele care este egal cu "H/u"
	 int nrnv=H/u;
	 //declar un vector auxiliar in care retin greutatea gutuilor culese pe fiecare nivel
	 int v[nrnv];
	 //initializez cu 0 vectorul "v"
	 for(i=0;i<nrnv;i++) v[i]=0;

	 //citesc din fisier greutatea si inaltimea fiecarei gutui
	 for(i=0;i<n;++i)
	 {
	  					  fscanf(f ,"%d" ,&a[i].h);
						  //vreau sa aflu inaltimea la care se afla cea mai de jos gutuie
	 					  if(hmin > a[i].h) hmin=a[i].h;
	 					  fscanf(f ,"%d" ,&a[i].g);
	 					  //memorez nivelul pe care se afla gutuia
	 					  a[i].nv=(H-a[i].h)/u;
	 					  //daca inaltimea este mai mica decat 0 sau mai mare decat "H" o ignor
	 					  if(a[i].h <=0 && a[i].h > H) i--;
   }
   //inchid fisierul de intrare
   fclose(f);

	 //sortez vectorul de structuri
   qsort(a,n,sizeof(fruct),fsort);

	 i=0;
	 //cat timp mai pot sa culeg gutui
	 while(hmin <= H && i < n)
	 {
	 				//retin in variabila "j" nivelul pe care se afla gutuia curenta
					j=a[i].nv;
					//atat timp cat nivelul este pozitiv
					while(j>=0)
					{
									//daca in vectorul "v" ,pozitia "j" nu este ocupata
									if(v[j]==0)
									{
													//memorez pe aceasta pozitie greutatea gutuii
													v[j]=a[i].g;
													//consider ca am cules gutuia respectiva
													max+=a[i].g;
													//crengile se ridica cu "u" centimetrii
													hmin+=u;
													break;
									}
					j--;
					}
		i++;
		}
		
		//scriu in fisierul "gutui.out" greutatea fructelor culese de Gigel
		FILE* fout=fopen("gutui.out","w");
		fprintf(fout ,"%d" ,max);
		fclose(fout);

		return 0;
}