Pagini recente » Cod sursa (job #2425042) | Cod sursa (job #786247) | Cod sursa (job #1996699) | Cod sursa (job #969298) | Cod sursa (job #438663)
Cod sursa(job #438663)
#include <stdio.h>
#include <stdlib.h>
#define FILEIN "gutui.in"
#define FILEOUT "gutui.out"
#define INFINIT 4294967295
#define NMAX 100002
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 comparator(const void * a, const void * b) {
return -1*(((gutuie*)a)->g - ((gutuie*)b)->g);
}
int main() {
FILE *fin = fopen(FILEIN, "r"), *fout = fopen(FILEOUT, "w");
int n, h, u, i;
long int totalsum = 0;
gutuie gutui[NMAX];
elem *start;
//citim datele intr-o lista de gutui
fscanf(fin, "%d %d %d", &n, &h, &u);
for (i=0; i<n; i++)
fscanf(fin, "%d %d", &gutui[i].h, &gutui[i].g);
//sfarsit citit date
//sortam datele
qsort(gutui, n, sizeof(gutuie), comparator);
//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
for (i=0; i<n; i++)
//vedem daca putem pune gutuia maxima in lista
if (insert(start, &gutui[i], h, u))
totalsum += gutui[i].g;
fprintf(fout, "%ld\n", totalsum);
fclose(fin);
fclose(fout);
return 0;
}