#include <stdlib.h>
#include <stdio.h>
#include <math.h>
//#include <conio.h>
typedef struct gutuie {
unsigned long H_gut; // intaltimea la care se afla gutuia
unsigned long G_gut; // greutatea gutuiei
unsigned long prioritate; // prioritatea culegerii gutuiei = nivel - 1
// prioritate 0 => gutuia trebuie culeasa imediat
} ;
/* OBS:
* - se va lucra doar cu primele x (< toleranta) gutui din vectorul de gutui sortat descrescator dupa greutate
* - dintre acestea de mai sus se vor selecta secvential gutuile de prioritate < toleranta (=nr maxim de gutui
* ce pot fi culese inainte ca index_min sa depaseasca H)
*/
void read_const (FILE* in, unsigned long *N, unsigned long *H, unsigned long *U) // citeste N,H,U
{ fscanf(in, "%lu", N);
fscanf(in, "%lu", H);
fscanf(in, "%lu", U);
// DEBUG purposes:
printf("Gutui in copac: %lu \n", *N);
printf("Inaltime Gigel: %lu \n", *H);
printf("Rata de inaltare: %lu \n", *U);
}
void read_gut (FILE *in, gutuie *gutui, unsigned long N) // citeste gutuile si le salveaza intr-un vector
{ for (int i=0; i<N; i++)
{ fscanf (in, "%lu", &gutui[i].H_gut);
fscanf (in, "%lu", &gutui[i].G_gut);
// DEBUG purposes:
//printf("Gutuia %i > %lum %lukg\n", i+1, gutui[i].H_gut, gutui[i].G_gut);
}
}
void set_prioritate (gutuie *gutui, unsigned long N, unsigned long U, unsigned long H, unsigned long *index_max, unsigned long *index_min)
{ unsigned long niv;
for (int i=0; i<N; i++)
{ niv = (unsigned long)floor(gutui[i].H_gut / U);
gutui[i].prioritate = (unsigned long)floor( (H-gutui[i].H_gut) / U);
if (niv>*index_max)
*index_max = niv;
if (niv<*index_min)
*index_min=niv;
// DEBUG purposes:
//printf("Gutuia %i > CONTROL %lu \n", i+1, gutui[i].H_gut / U);
//printf("Gutuia %i > prioritate %lu\n", i+1, gutui[i].prioritate);
}
}
void print_gutui (gutuie *gutui, unsigned long N)
{ printf("Format:\n\tGutuia nrcrt > \tH_gut \tG_gut \t[prioritate]\n");
for (int i=0; i<N; i++)
printf("\tGutuia %i > \t%lum \t%lukg \t[%lu]\n", i+1, gutui[i].H_gut, gutui[i].G_gut, gutui[i].prioritate);
}
int compare (const void *g1, const void *g2) // pt sortate descrescatoare dupa greutate
{
return (int)((*(gutuie*)g2).G_gut - (*(gutuie*)g1).G_gut);
}
int compare_priori (const void *g1, const void *g2) // pt sortate crescatoare dupa prioritate
{
if (((*(gutuie*)g1).prioritate - (*(gutuie*)g2).prioritate) == 0) // in caz de egalitate
return (int)((*(gutuie*)g2).G_gut - (*(gutuie*)g1).G_gut); // alege gutuia de greutate mai mare
return (int)((*(gutuie*)g1).prioritate - (*(gutuie*)g2).prioritate);
}
void truncate (gutuie *vechi, gutuie *nou, unsigned long toleranta)
{ for (int i=0; i<toleranta; i++)
nou[i]=vechi[i];
}
/*
void sum (gutuie *gutui_best, unsigned long n)
{ unsigned long sum = 0;
FILE *out = fopen ("gutui.out", "wt");
for (int i=0; i<n; i++)
{ sum+=gutui_best[i].G_gut;
//printf("\tGutuia %i > \t%lum \t%lukg \t[%lu]\n", i+1, gutui_best[i].H_gut, gutui_best[i].G_gut, gutui_best[i].prioritate);
}
fprintf(out, "%lu",sum);
fclose(out);
// DEBUG purposes:
printf("Suma maxima: %lu\n",sum);
}
*/
void sum (gutuie *gutuie_current, gutuie *gutuie_stop, unsigned long offset, unsigned long N, unsigned long *suma)
{ if (gutuie_current == gutuie_stop || offset > N)
return;
printf ("prioritate gutuie-off: %lu\n", (double)(gutuie_current->prioritate) - (double)offset);
if ((double)(gutuie_current->prioritate) - (double)offset >= 0)
{ printf ("suma + g: %lu\n", *suma + gutuie_current->G_gut);
*suma += gutuie_current->G_gut;
sum ((gutuie_current+1), gutuie_stop, (offset+1), N, suma); }
else
sum ((gutuie_current+1), gutuie_stop, offset, N, suma);
}
int main()
{ unsigned long N; // numarul de gutui din copac
unsigned long H; // inaltime maxima Gigel
unsigned long U; // rata de inaltare a gutuilor
unsigned long Gmax=0; // greutatea maxima culeasa de Gigel
unsigned long index_max=0; // nivelul MAXIM al sirului de gutui accesibile (cele mai de SUS gutui la care poate ajunge Gigel)
unsigned long index_min=(unsigned long)pow(2,sizeof(long)-1); // nivelul MAXIM al sirului de gutui accesibile (cele mai de JOS gutui la care poate ajunge Gigel)
// nivel = inaltime_gutuie % rata_intaltare
unsigned long niv_max; // = H / U
unsigned long toleranta; // numarul maxim de gutui pe care le pot culege inainte de a depasi H
gutuie *index;
FILE* in = NULL;
in = fopen("gutui.in","rt");
if (!in)
{ printf("Error opening input file\n");
return 1;
}
read_const (in,&N,&H,&U);
gutuie gutui[N];
read_gut (in,gutui,N);
fclose(in);
set_prioritate(gutui,N,U,H,&index_max,&index_min);
niv_max = (unsigned long)floor(H/U);
toleranta = niv_max - index_min + 1;
printf("Index maxim: %lu\nIndex minim: %lu\nToleranta: %lu\n", index_max, index_min, toleranta);
printf("Compare: %i\n", compare(&gutui[0],&gutui[1]));
qsort (gutui, N, sizeof(gutuie), compare_priori);
print_gutui (gutui,N);
index = gutui;
sum (index, index+N, 0, N, &Gmax);
printf("Suma maxima: %lu\n", Gmax);
FILE *out = fopen ("gutui.out", "wt");
if (!out)
{ printf("Error opening output file\n");
return 2;
}
/* if (toleranta<N)
{ gutuie gutui_best[toleranta];
truncate (gutui, gutui_best, toleranta);
sum(gutui_best,toleranta);
}
else
sum(gutui,N);
*/
fprintf (out, "%lu", Gmax);
fclose(out);
//printf("------------------\n");
// getch();
return 0;
}