Pagini recente » Cod sursa (job #2068136) | Cod sursa (job #1078749) | Cod sursa (job #2396302) | Cod sursa (job #2267147) | Cod sursa (job #432583)
Cod sursa(job #432583)
#include <stdio.h>
#include <stdlib.h>
/* Variabile globale */
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; // auxiliar
// 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", &h[i], &g[i]);
}
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)
long maxDone; // nivelul pana la care a fost cules numarul maxim de gutui
// calcul k
k = 0;
for (i = 0; i<N; i++)
if ((H-h[i])/U + 1 > k && H-h[i]>=0)
k = (H-h[i])/U + 1;
// 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;
maxDone = 0;/*
while (maxDone < k && !done){
jMax = 0;
for (j = 0; j < N; j++){
// cautam cea mai grea gutuie pe care o putem culege
// conditia e ca maxDone < kj, unde kj = nivelul gutuii j, adica (H-h[j])/U + 1, iar maxDone e nivelul maxim sub care(inclusiv el) nu mai putem culege
if (H-h[j] >=0){
kj = (H - h[j])/U + 1;
if (kj <= maxDone)
g[j] = 0;
if (g[j] > g[jMax])
jMax = j;
}
else{
g[j] = 0;
}
}
// actualizam gMax, picked, i si done
if (g[jMax] <= 0)
done = 1;
else{
gMax += g[jMax];
g[jMax] = 0;
for (j = (H-h[jMax])/U + 1; j<k+1; j++){
picked[j] ++;
if (picked[j]==j && j>maxDone){
maxDone = j;
}
}
}
}
*/
free (g);
free (h);
free (picked);
}