Cod sursa(job #441400)

Utilizator corina_stemateStemate Corina Stefania corina_stemate Data 12 aprilie 2010 21:50:47
Problema Gutui Scor 80
Compilator c Status done
Runda teme_upb Marime 2.56 kb
//Stemate Corina 325CA

#include <stdio.h>
#include <string.h>
#include <stdlib.h>


//tipul gutuie
typedef struct{
	unsigned int h;	//inaltimea la care se afla gutuia
	unsigned int g; //greutatea gutuii
	unsigned int p; //pasul pana la care se poate culege gutuia
}gutuie;


//functie de comparatie folosita pt sortarea gutuilor crescator dupa pas si in caz de egalitate descrescator dupa greutate
int comp(const void *a,const void* b){
gutuie* x=(gutuie*)a;
gutuie* y=(gutuie*)b;
if ( x->p==y->p) return y->g-x->g ;
return x->p-y->p;
}

int main(){

//fisierul de citire
FILE *f;
f=fopen("gutui.in","r");

//n=nr de gutui
//h=inaltimea pana la care ajunge Gigel
//u=inaltimea cu care se inalta gutuiul
unsigned int n,h,u;

fscanf(f,"%d %d %d",&n,&h,&u);


//retinem gutuile intr-un vector si calculam pt fiecare pasul
int i,j;
gutuie *x,aux;
x=(gutuie*)malloc(n*sizeof(gutuie));

for (i=0;i<n;i++){
	fscanf(f,"%d %d\n",&x[i].h,&x[i].g);
	if (x[i].h > h) x[i].p=-1;
		else x[i].p=(h-x[i].h)/u;
}
fclose(f);
/*
for (i=0;i<n;i++)
	for (j=i+1;j<n;j++)
		if (x[i].p > x[j].p) {
					aux.h=x[i].h;
					aux.g=x[i].g;
					aux.p=x[i].p;
					x[i].h=x[j].h;
					x[i].g=x[j].g;
					x[i].p=x[j].p;
					x[j].h=aux.h;
					x[j].g=aux.g;
					x[j].p=aux.p;
		}
		else if (x[i].p==x[j].p){
				if (x[i].g < x[j].g) {
					aux.h=x[i].h;
					aux.g=x[i].g;
					x[i].h=x[j].h;
					x[i].g=x[j].g;
					x[j].h=aux.h;
					x[j].g=aux.g;
		}
}
*/
//sortam gutuile crescator dupa pas si descrescator dupa greutate in caz de egalitate
qsort(x,n,sizeof(gutuie),comp);

//vectorul de solutii
gutuie *s;
s=(gutuie*)malloc(n*sizeof(gutuie));

//k =nr de gutui din solutie
int k=0;

//se construieste solutia
i=0;
int min;

//pt fiecare gutuie
while (i<n){
	//daca se afla mai sus decat inaltimea la care ar fi putut ajunge gigel la inceput se sare peste
	if (x[i].p<0) i++;
	//altfel
	else{
		//daca gutuia putea fi culeasa la pasul respectiv se culege
		if (x[i].p>=k) {
			s[k].p=x[i].p;
			s[k].g=x[i].g;
			s[k].h=x[i].h;
			i++;
			k++;
		}
		//altfel se cauta gutuia deja culeasa cu greutatea minima , si daca aceasta e mai mica decat gutuia actuala se inlocuieste in solutie gutuia deja culeasa cu noua gutuie
		else{
			if (k==0) i++;
				else {
					min=0;
					for(j=1;j<k;j++)
						if (s[j].g<s[min].g) min=j;
					if (x[i].g>s[min].g) {
							s[min].g=x[i].g;
							s[min].h=x[i].h;
							s[min].p=x[i].p;
					}
					i++;
				}
		}
	}
}

//calculam nr de kg al gutuilor din solutie
int kg=0;
for (i=0;i<k;i++)
	kg=kg+s[i].g;


//afisam solutia
FILE *g;
g=fopen("gutui.out","w");
fprintf(g,"%d",kg);
fclose(g);

return 0;
}