Pagini recente » Cod sursa (job #2345398) | Cod sursa (job #672405) | Cod sursa (job #440491) | Cod sursa (job #106011) | Cod sursa (job #433662)
Cod sursa(job #433662)
#include <stdio.h>
#include <stdlib.h>
#define FILEIN "gutui.in"
#define FILEOUT "gutui.out"
#define DISPLAY 0
typedef struct gutuie {
int g, h;
} gutuie;
int main() {
FILE *fin = fopen(FILEIN, "r"), *fout = fopen(FILEOUT, "w");
int n, h, u, i, j, pick[500], max, maxpoz, totalsum = 0, k;
gutuie gutui[500];
fscanf(fin, "%d %d %d", &n, &h, &u);
for (i=1; i<=n; i++)
fscanf(fin, "%d %d", &gutui[i].h, &gutui[i].g);
//initializam vectorul de pozitii ocupate
for (i=0; i<=h/u + 1; i++)
pick[i] = 0;
//gasim gutuia cu greutatea maxima de n ori
for (i=1; i<=n; i++) {
max = -1;
maxpoz = 0;
//luam urmatoarea gutuie maxima
for (j=1; j<=n; j++)
if (max < gutui[j].g) {
max = gutui[j].g;
maxpoz = j;
}
if (DISPLAY) printf("Incerc sa adaug (%d, %d) la lant. Caut unde incepand cu poz %d pana la %d\n", gutui[maxpoz].g, gutui[maxpoz].h, h/u-(gutui[maxpoz].h)/u + !((gutui[maxpoz].h)%u), 1-(h%u)%2);
//vedem daca putem pune gutuia maxima
for (j=h/u-(gutui[maxpoz].h)/u + !((gutui[maxpoz].h)%u); j >= 1-(h%u)%2; j--) {
if (!pick[j]) {
if (DISPLAY) printf("Am adaugat gutuia pe poz %d\n", j);
pick[j] = 1;
if (DISPLAY) {
for (k=1; k<=h/u; k++)
printf("%d ", pick[k]);
printf("\n");
}
totalsum += gutui[maxpoz].g;
break;
}
}
if (DISPLAY) printf("Suma partiala %d\n", totalsum);
gutui[maxpoz].g = -1;
}
if (DISPLAY) printf("%d\n", totalsum);
fprintf(fout, "%d\n", totalsum);
fclose(fin);
fclose(fout);
return 0;
}