Pagini recente » Cod sursa (job #520152) | Cod sursa (job #127588) | Cod sursa (job #1761188) | Cod sursa (job #245095) | Cod sursa (job #432444)
Cod sursa(job #432444)
#include <stdio.h>
#include <stdlib.h>
/* Variabile globale */
//long ** g; // gutuile sunt inregistrate intr-un vector de vectori in functie de nivelul (H-Hgutuie)/U la care se gaseste gutuia
long * g; // vectorul de gutui (greutati)
long * h; // vectorul de inaltimi per gutuie
long N; // nr de gutui
long H; // inaltimea maxima la care ajunge Gigel
long U; // cu cat se ridica ramurile dupa culegerea unei gutui
long gMax; // greutatea maxima culeasa
/* Declaratii functii */
void citire(); // citirea fisierului de intrare
void afisare(); // afisarea rezultatelor
void rezolvare(); // rezolvaea problemei
/* Main */
int main(int argc, char *argv[]) {
citire(); // citire date de intrare
rezolvare(); // rezolvare problema
afisare(); // afisare rezultate
return 0;
}
/* Definitii functii */
/* citirea fisierului de intrare */
void citire() {
FILE * in; // fisier de intrare
long i,gg,hg; // auxiliari
// deschidem fisier de intrare
in = fopen("gutui.in","rt");
fscanf(in, "%ld%ld%ld", &N, &H, &U); // citire N, H, U
// alocam memorie pentru vectorul de gutui si cel de inaltimi
g = malloc (N * sizeof(long));
h = malloc (N * sizeof(long));
for (i=0;i<N;i++){
// citire gutui
fscanf(in, "%ld %ld", &hg, &gg);
g[i] = gg;
h[i] = hg;
}
gMax = 0; // initializare gMax
// inchidem fisier de intrare
fclose(in);
}
/* afisarea rezultatelor */
void afisare() {
FILE * out; // fisier de iesire
// deschidem fisier de iesire
out = fopen("gutui.out","wt");
fprintf(out,"%ld", gMax);
// inchidem fisier de iesire
fclose(out);
}
/* Rezolvarea problemei */
void rezolvare() {
long * picked; // picked[i] = cate gutui au fost culese de pe niveluri <= i, maximul acceptat fiind i
long k; // numar de niveluri ale pomului
long i,j,jMax,kj; // auxiliari
int done; // semnaleaza ca nu mai sunt gutui de cules (greutatea maxima ce poate fi culeasa e 0)
// calcul k
k = 0;
for (i = 0; i<N; i++)
if ((H-h[i])/U + 1 > k)
k++;
// alocam memorie si initializam picked
picked = malloc ((k+1) * sizeof(long));
for (i = 0; i<k+1; i++)
picked[i] = 0;
i=0;
done = 0;
while (i<N && picked[k] < k && !done){
jMax = 0;
for (j = 0; j < N; j++){
// cautam cea mai grea gutuie pe care o putem culege
// conditia e ca picked[kj] < kj, unde kj = nivelul gutuii j, adica (H-h[j])/U + 1
kj = (H - h[j])/U + 1;
if (g[j] > g[jMax] && picked[kj] < kj)
jMax = j;
}
// actualizam gMax, picked, i si done
if (g[jMax] <= 0)
done = 1;
gMax += g[jMax];
g[jMax] = 0;
for (j = (H-h[jMax])/U + 1; j<k+1; j++)
picked[j] ++;
i++;
}
free (g);
free (h);
free (picked);
}