Pagini recente » Cod sursa (job #435897) | Cod sursa (job #1443906) | Cod sursa (job #1581470) | Cod sursa (job #1593585) | Cod sursa (job #432645)
Cod sursa(job #432645)
#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
void quick(long left,long right); // quicksort
long pos(long left,long right); // determinarea pivotului la quicksort
/* 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;
// sortam vectorii prin metoda quicksort in functie de greutatea gutuilor
quick(0,N);
j=0;
done = 0;
maxDone = 0;
while (j < N && maxDone < k){
// la pozitia curenta j avem cea mai grea gutuie neculeasa, trebuie sa verificam daca avem voie sa o culegem
// 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){
// daca inaltimea la care avem gutuia < H
// calculam nivelul gutuii
kj = (H - h[j])/U + 1;
if (kj > maxDone){
// avem voie sa o culegem
gMax += g[j];
for (i = (H-h[j])/U + 1; i<k+1; i++){
picked[i] ++;
if (picked[i]==i && i>maxDone)
maxDone = i;
}
}
}
j++;
}
free (g);
free (h);
free (picked);
}
long pos(long left,long right){
long i=left,j=right,direction=1;
long aux;
while (i<j){
if (g[i]<g[j]){
// facem swap intre cele doua jumatati
aux=g[i];
g[i]=g[j];
g[j]=aux;
aux=h[i];
h[i]=h[j];
h[j]=aux;
if (direction==1)
direction=0;
else
direction=1;
}
if (direction==1)
j--;
else
i++;
}
return i;
}
void quick(long left,long right){
long k;
if (left<right){
k=pos(left,right);
quick(left,k-1);
quick(k+1,right);
}
return;
}