#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
typedef struct fruct{ //am considerat o structura pentru gutui, ce contine atributele de mai jos
unsigned long int inaltime;
unsigned long int greutate;
unsigned long int indice;
}Gutui;
unsigned long int compare(struct fruct *elem1, struct fruct *elem2)//functie de comparare, pentru qsort
{ //sorteaza descrescator, in functie de indicele fiecarei gutui
if ( elem1->indice > elem2->indice)
return -1;
else if (elem1->indice < elem2->indice)
return 1;
else
return 0;
}
int main(){
Gutui s[100001]; //initializez un vector de gutui
unsigned long int N, H, U;
unsigned long int U2;
unsigned long int i,j,k;
unsigned long int max;
unsigned long int G=0;
FILE *fin, *fout;
fin = fopen("gutui.in" , "rt");
if(!fin) printf(" eroare la deschidere fisier input");
else
{
fscanf(fin, "%lu", &N);//citesc numarul de gutui
fscanf(fin, "%lu", &H);//inaltimea maxima la care ajunge Gigel
fscanf(fin, "%lu", &U);// inaltimea cu care creste nivelul fiecarei gutui, la culegerea unui fruct
printf("%lu %lu %lu\n", N, H, U);
for(i = 0 ; i < N ; i++) //citesc din fisier atributele fiecarei gutui
{
fscanf(fin, "%lu", &s[i].inaltime);
fscanf(fin, "%lu", &s[i].greutate);
}
for(i = 0 ; i < N ; i++)
printf("%lu %lu\n",s[i].inaltime,s[i].greutate);
printf("\n");
for(i=0;i< N;i++) //completez campul de indice al fiecare gutui, dupa formula de mai jos
s[i].indice= (H - s[i].inaltime)/U+1; //formula de calcul al indicelui care spune cate gutui mai pot fi culese dupa gutuia i
for(i = 0 ; i < N ; i++)
printf("%lu %lu %lu\n",s[i].inaltime,s[i].greutate, s[i].indice);
printf("\n");
qsort((void *) &s, N, sizeof(struct fruct),(void *)compare ); //sortare descrescatoare dupa indice
for(i = 0 ; i < N ; i++)
printf("%lu %lu %lu\n",s[i].inaltime,s[i].greutate,s[i].indice);
printf("\n");
i=0;
int poz;//pozitia din care extrag maximul
int indice=s[0].indice;
while(indice>0 )
{
j=0;
max=0;
while(s[j].indice==indice && j<N){ //numar gutuile cu acelasi indice (maxim pentru sirul de gutui)
j++;
}
printf("\n");
printf("j=%i\n",j);
printf("N=%i\n",N);
for(k=0;k<j;k++)
if(max<=s[k].greutate){ //caut greutatea maxima , pentru gutuile cu acelasi indice maxim
max=s[k].greutate;
poz=k; //retin pozitia pe care se afla
}
G+=max;//adaug la greutatea culeasa
for(k=poz; k<N-1;k++) //extrag din sir gutuia culeasa
s[k]=s[k+1];
N--; //micsorez de asemenea si lungimea sirului
for(k=0;k<j;k++)if(s[k].indice>indice - 1)s[k].indice=indice-1; //reactualizez indicii (maxim devine maxim-1)
printf("G=%i\n",G);
for(i = 0 ; i < N ; i++)
printf("%lu %lu %lu\n",s[i].inaltime,s[i].greutate,s[i].indice);
printf("\n");
indice--; //scad si indicele, pentru a trece la urmatoarele elemente din sir
}
/* fout=fopen("gutui.out", "wt");
if(!fout) printf("eroare deschidere fisier pentru scriere");
else
fprintf(fout, "%i",G); //scriu rezultatul in fisierul de output
*/
}
fclose(fin);
getch();
}