Cod sursa(job #439265)

Utilizator oana.vasiuVasiu Oana-Alexandra oana.vasiu Data 11 aprilie 2010 14:50:22
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 2.64 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;

struct nod{
int val;
struct nod* leg;
}Node;


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){
//	printf("il scriu pe primul in lista\n");
	
	lst=nou;
	return lst;
	}
if (v<=lst->val){
//	printf("scriu la inceput\n");
	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;

//printf("prima val este %i   %i\n",q->val,p->val);
while ((p->leg!=NULL) && (v >= p->val)){
//	printf("q->val=%i  p->val=%ikhg\n",q->val,p->val);	
	q=p;
	p=p->leg;
}
if (v<p->val){
q->leg=nou;
nou->leg=p;
//printf("scriu in lista\n");
} else p->leg=nou;
return lst;


}

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;
	}
}

int comparatorpasi(struct gutui *a, struct gutui *b){
	return (a->nr_pasi - b->nr_pasi);
}
int comparatorg(struct gutui *a, struct gutui *b){
	return (b->g - a->g);
}


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;
long max = 0;

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;
	if ((max < v[i].nr_pasi) && (v[i].h <= H)) max = v[i].nr_pasi;
	v[i].marcat = 0;
	}
	
		
printf("%li\n", max);
qsort(v, n, sizeof(struct gutui), (compfn)comparatorg);


printf("\n");
qsort(v, n, sizeof(struct gutui), (compfn)comparatorpasi);
//for (i = 0; i < n; i++)
  //      printf("%li   %li   %li\n", v[i].h, v[i].g, v[i].nr_pasi);
printf("\n");
long suma = 0;
int j;
int pasi=1;


struct nod* lista=NULL;
for (i=0; i<n; i++){
//	for (j = 0; j < n; j++)
  //	      printf("%li   %li   %li\n", v[j].h, v[j].g, v[j].nr_pasi);
	//printf("\n");
	if (v[i].nr_pasi >= pasi){
			
		
	//	printf("se aduna la suma %li\n", v[i].g);
		lista=add(lista,v[i].g);		 
	//	print(lista);		
		suma = suma + v[i].g;
		 pasi++;
	//	printf("pasi=%i\n",pasi);
	
	}
	else if (lista->val < v[i].g){
		
	//	printf("sa scade %i\n", lista->val);		
		suma=suma-lista->val;
		lista=add(lista,v[i].g);		
		lista=lista->leg;	
	//	printf("se aduna %li\n", v[i].g);
				
		suma=suma+v[i].g;
	//	print(lista);
	}
}

printf("%li",suma);
fprintf(g,"%li",suma);
fclose(f); 
fclose(g);
return 0;
}