Pagini recente » Cod sursa (job #607416) | Cod sursa (job #3219218) | Cod sursa (job #3162641) | Cod sursa (job #2049005) | Cod sursa (job #438039)
Cod sursa(job #438039)
#include <stdio.h>
#include <stdlib.h>
#define FILEIN "gutui.in"
#define FILEOUT "gutui.out"
#define INFINIT 4294967295
typedef struct gutuie {
int g, h;
gutuie *next;
} gutuie;
typedef struct elem {
unsigned int val;
elem *next;
} elem;
int insert(elem *start, gutuie *gutui, int h, int u) {
unsigned int nivel_maxim_gutuie = (h-gutui->h)/u;
int out_of_bounds = 0;
elem *p = start->next, *previous = start, *nou;
//parcurgem de la final toate gutuile puse pana atunci
while (p) {
//daca gutuia curenta poate fi pusa mai tarziu decat gutuia noua
if (p->val >= nivel_maxim_gutuie) {
//trecem la urmatoarea gutuie
if (p->val == nivel_maxim_gutuie) {
if (nivel_maxim_gutuie)
nivel_maxim_gutuie--;
else
out_of_bounds = 1;
}
previous = p;
p = p->next;
}
//daca am ajuns la punctul la care am putea sa adaugam, verificam daca se poate
else {
//daca o putem adauga
if ((previous->val - nivel_maxim_gutuie) && (nivel_maxim_gutuie - p->val) && nivel_maxim_gutuie >= 0) {
//adaugam noua gutuie intre previous si p
nou = (elem*)malloc(sizeof(elem));
nou->val = nivel_maxim_gutuie;
nou->next = p;
previous->next = nou;
return 1;
}
//daca nu se poate adauga
else
return 0;
} //end verificare si adaugare
}//end while
//daca am ajuns pana aici inseamna ca ar trebui sa incercam la inceputul listei
if ((previous->val - nivel_maxim_gutuie) && !out_of_bounds) {
nou = (elem*)malloc(sizeof(elem));
nou->val = nivel_maxim_gutuie;
nou->next = previous->next;
previous->next = nou;
return 1;
}
return 0;
}
int main() {
FILE *fin = fopen(FILEIN, "r"), *fout = fopen(FILEOUT, "w");
int n, h, u, i;
long int totalsum = 0;
gutuie *gutui, *nou, *p, *prev, *gutuiend;
elem *start;
//citim datele intr-o lista de gutui
fscanf(fin, "%d %d %d", &n, &h, &u);
gutui = (gutuie*)malloc(sizeof(gutuie));
fscanf(fin, "%d %d", &gutui->h, &gutui->g);
gutui->next = NULL;
gutuiend = gutui;
for (i=2; i<=n; i++) {
nou = (gutuie*)malloc(sizeof(gutuie));
fscanf(fin, "%d %d", &nou->h, &nou->g);
p = gutui;
//daca trebuie pusa in capul listei
if (p->g <= nou->g) {
nou->next = p;
gutui = nou;
continue;
}
//daca trebuie pusa la sfarsitul listei
if (gutuiend->g >= nou->g) {
if (!gutuiend->next) {
gutuiend->next = nou;
nou->next = NULL;
gutuiend = nou;
continue;
} else p = gutuiend;
}
//daca am ajuns aici atunci sigur nu trebuie pusa in capul listei
prev = p;
p = p->next;
while (p && p->g > nou->g) {
prev = p;
p = p->next;
}
prev->next = nou;
nou->next = p;
gutuiend = nou;
}
//sfarsit citit date
//initializam lista de gutui care le culegem
start = (elem*)malloc(sizeof(elem));
start->val = INFINIT;
start->next = NULL;
//luam gutuile in ordinea descrescatoare a greutatii
p = gutui;
for (i=1; i<=n; i++) {
//vedem daca putem pune gutuia maxima in lista
if (insert(start, p, h, u)) {
totalsum += p->g;
}
p = p->next;
}
fprintf(fout, "%ld\n", totalsum);
fclose(fin);
fclose(fout);
return 0;
}