Cod sursa(job #434833)

Utilizator PacoGeorgescu Claudiu Paco Data 6 aprilie 2010 17:03:47
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 1.78 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct gutui{
	int h;
	int g;
} gutui;

typedef struct node {
	gutui fr;
	struct node* next;
} node;

int partitie(gutui x[],int s,int d){
	int piv=x[s].h;
	int j=d+1,i=s-1;
	gutui aux;		
	while(1){
		do{j--;} while(x[j].h<piv);
		do{i++;} while(x[i].h>piv);
		if (i<j){
			aux=x[i];
			x[i]=x[j];
			x[j]=aux;
		}
	else return j;
		}
	}
void quicksort(gutui x[],int s,int d){
		if(s<d){
			int p=partitie(x,s,d);
			quicksort(x,s,p);
			quicksort(x,p+1,d);
		}
	}

int main(){
	FILE *f=fopen("gutui.in","r");
	FILE *g=fopen("gutui.out","w");
	int u,h,n,i;
	gutui *fr;
	node** zona;
	fscanf(f,"%d%d%d",&n,&h,&u);
	fr=(gutui*)malloc(n*sizeof(gutui));
	for (i=0;i<n;i++)
		fscanf(f,"%d%d",&fr[i].h,&fr[i].g);
	//quicksort(fr,0,n-1);
	node *p,*q;	
	int k=h/u+1,niv;
	zona=(node**)calloc(k,sizeof(node*));
	for (i=0;i<n;i++)
		if (fr[i].h<=h){
			p=(node*)malloc(sizeof(node));
			p->fr=fr[i];
			niv=k-1-(100-fr[i].h)/u;
			if (zona[niv]==NULL){
				p->next=NULL;
				zona[niv]=p;
			}
			else
				if (zona[niv]->fr.g<fr[i].g){
					p->next=zona[niv];
					zona[niv]=p;
				}
			else{
					q=zona[niv];
					while(q->next!=NULL&&q->next->fr.g>p->fr.g)
						q=q->next;
					p->next=q->next;
					q->next=p;
					}
		}
	/* 
	for (i=0;i<k;i++){
		p=zona[i];
		if (p==NULL) printf("gol");
		while(p!=NULL){
			printf("%d %d : ",p->fr.h,p->fr.g);
			p=p->next;
		}
		printf("\n");
	}
	*/ 
	int j=1,max,poz,s=0;		
	while (1){
		max=-1;
		poz=-1;
		for (i=0;i<j;i++)
			if(zona[i]!=NULL&&zona[i]->fr.g>max){
				max=zona[i]->fr.g;
				poz=i;
				}
		if (poz!=-1){
			//printf("Am ales %d %d\n",zona[poz]->fr.h,zona[poz]->fr.g);
			s+=zona[poz]->fr.g;
			zona[poz]=zona[poz]->next;
		}
		j++;   
		if (j==k+1) break;
	}		
	fprintf(g,"%d\n",s); 
	fclose(f);
	fclose(g);
	return 0;
}