Pagini recente » Cod sursa (job #1866748) | Cod sursa (job #3254925) | Cod sursa (job #1210925) | Cod sursa (job #1974435) | Cod sursa (job #433818)
Cod sursa(job #433818)
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define FILEIN "gutui.in"
#define FILEOUT "gutui.out"
#define INFINIT -999999
#define DISPLAY 0
typedef struct gutuie {
int g, h;
} gutuie;
typedef struct elem {
int val;
elem *next;
} elem;
int insert(elem *start, gutuie gutui, int u) {
elem *p = start->next, *previous = start, *nou;
//parcurgem de la final toti maximii alesi pana atunci
while (p) {
if (DISPLAY) { printf("Suntem la gutuia de inaltime %d. Comparam cu %d. ", p->val, gutui.h); fflush(stdout); }
//daca elementul curent e mai jos decat ce adaugam
if (p->val < gutui.h) {
if (DISPLAY) { printf("Gutuia curenta e mai jos. Trecem la urmatoarea\n"); fflush(stdout); }
//trecem la urmatorul element
previous = p;
p = p->next;
}
//daca am ajuns la punctul la care am putea sa adaugam, verificam daca se poate
else if (ceil((float)gutui.h/u) - ceil((float)p->val/u)) {
if (DISPLAY) { printf("Gutuia curenta e deasupra gutuii pe care incercam sa o adaugam. Incercam s-o bagam pe cea noua\n"); fflush(stdout); }
//daca nu suntem la capatul listei
if (p->next) {
nou = (elem*)malloc(sizeof(elem));
nou->val = gutui.h;
nou->next = p->next;
p->next = nou;
return 1;
}
else { //daca suntem la capatul listei
nou = (elem*)malloc(sizeof(elem));
nou->val = gutui.h;
nou->next = p->next;
p->next = nou;
return 1;
}
}
else {
if (DISPLAY) { printf("Nu am putut adauga gutuia noua (nu indeplinea conditiile)\n"); fflush(stdout); }
return 0;
}
}
if (DISPLAY) { printf("Incercam sa adaugam gutuia la inceputul listei (nivelele sunt %f si %d)... ", ceil((float)gutui.h/u), previous->val/u); fflush(stdout); }
if (ceil((float)gutui.h/u) - ceil((float)previous->val/u)) {
if (DISPLAY) { printf("OK\n"); fflush(stdout); }
nou = (elem*)malloc(sizeof(elem));
nou->val = gutui.h;
nou->next = previous->next;
previous->next = nou;
return 1;
}
if (DISPLAY) { printf("Nu a mers\n"); fflush(stdout); }
return 0;
}
int main() {
FILE *fin = fopen(FILEIN, "r"), *fout = fopen(FILEOUT, "w");
int n, h, u, i, j, max, maxpoz, totalsum = 0;
gutuie gutui[500];
elem *start;
start = (elem*)malloc(sizeof(elem));
start->val = INFINIT;
start->next = NULL;
fscanf(fin, "%d %d %d", &n, &h, &u);
for (i=1; i<=n; i++)
fscanf(fin, "%d %d", &gutui[i].h, &gutui[i].g);
//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. ", gutui[maxpoz].g, gutui[maxpoz].h); fflush(stdout); }
//vedem daca putem pune gutuia maxima in lista
if (insert(start, gutui[maxpoz], u)) {
if (DISPLAY) { printf("Am adaugat gutuia\n"); fflush(stdout); }
totalsum += gutui[maxpoz].g;
}
else if (DISPLAY) { printf("Nu am adaugat gutuia\n"); fflush(stdout); }
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;
}