Cod sursa(job #439971)

Utilizator oana.vasiuVasiu Oana-Alexandra oana.vasiu Data 11 aprilie 2010 21:08:00
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 2.39 kb
#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;
}