Pagini recente » Cod sursa (job #699268) | Cod sursa (job #1770193) | Cod sursa (job #3156439) | Cod sursa (job #1678597) | Cod sursa (job #439315)
Cod sursa(job #439315)
#include<stdio.h>
#include<stdlib.h>
struct gutui{
long h;
long g;
long nr_pasi;
int marcat;
};
typedef int (*compfn)(const void*, const void*);
long n, H, U;
//declarare nod lista ordonata
struct nod{
int val;
struct nod* leg;
}Node;
//functie pt adaugare in lista ordonata
struct nod* add(struct nod* lst,int v){
struct nod *nou = (struct nod *)malloc(sizeof(struct nod));
struct nod* p = (struct nod *)malloc(sizeof(struct nod));
nou->val = v;
nou->leg = NULL;
if (lst == NULL){
lst = nou;
return lst;
}
if (v <= lst->val){
nou->leg = lst;
lst = nou;
return lst;
}
if ((v > lst->val ) && ( lst->leg == NULL )){
lst->leg = nou;
return lst;
}
struct nod* q = (struct nod *)malloc(sizeof(struct nod));
p = lst;
q = p;
p = lst->leg;
while ((p->leg != NULL) && (v >= p->val)){
q = p;
p = p->leg;
}
if (v < p->val){
q->leg = nou;
nou->leg = p;
} else p->leg = nou;
return lst;
}
//functie pentru afisare lista(de verficare)
void print(struct nod *lst){
struct nod* p = (struct nod *)malloc(sizeof(struct nod));
p = lst;
while (p != NULL){
printf("%i\n",p->val);
p = p->leg;
}
}
//functia comparator folosita de qsort in functie de numarul de pasi
int comparatorpasi(struct gutui *a, struct gutui *b){
return (a->nr_pasi - b->nr_pasi);
}
int main(){
FILE* f = fopen("gutui.in","r");
FILE* g = fopen("gutui.out", "w");
fscanf(f,"%li %li %li",&n,&H,&U);
printf("%li %li %li \n",n,H,U);
struct gutui v[n];
long i;
//citire date initiale intr-un vector de structuri
for (i = 0 ; i < n ; i++){
fscanf(f,"%li %li", &v[i].h, &v[i].g);
v[i].nr_pasi = (( H - v[i].h ) / U) + 1 ;
if (v[i].h > H) v[i].nr_pasi=0;
v[i].marcat = 0;
}
//sortare dupa numarul de pasi
qsort(v, n, sizeof(struct gutui), (compfn)comparatorpasi);
long suma = 0;
int pasi = 1;//numarulde pasi efectuati
struct nod* lista = NULL;
for (i = 0; i < n; i++){
if (v[i].nr_pasi >= pasi){
//daca se poate ajunge la gutuie ea se aduna la suma si se adauga in lista
lista = add(lista,v[i].g);
suma = suma + v[i].g;
pasi++;
//dupa ce s-a adaugat o gutuie numarul de pasi creste(creste inaltimea gutuilor)
}
else if (lista->val < v[i].g){
// se scoate o gutuie si se puna alta in schimb
suma = suma - lista->val;
lista = add(lista,v[i].g);
lista = lista->leg;
// se aduna v[i].g
// se scade primul element din lista
suma = suma + v[i].g;
}
}
fprintf(g,"%li",suma);
fclose(f);
fclose(g);
return 0;
}