Cod sursa(job #439041)

Utilizator ana.ionana ion ana.ion Data 11 aprilie 2010 12:13:09
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 1.89 kb
#include<stdio.h>
#include<stdlib.h>
typedef struct fruct{	//structura in care retine datele despre fiecare gutuie: ht-inaltime; wt-greutate; niv-nivel relativ la h si u
	unsigned int ht;
	unsigned int wt;
	unsigned int niv;
} fruct;
int compare ( const void * a, const void * b){	//functia de compare folosita in qsort
	fruct f1, f2;
	f1 = *(fruct*)a;
	f2 = *(fruct*)b;
	return f2.wt-f1.wt;
}
int main (){
	FILE * fin = fopen ( "gutui.in", "r");	//deschid fisier de intrare
	FILE * fout = fopen ( "gutui.out", "w");	//deschid fisier de iesire
	long n, u, h;
	int i, prada=0, j, maxim=0;
	fscanf( fin, "%ld", &n);
	fscanf( fin, "%ld", &h);
	fscanf( fin, "%ld", &u);
	fruct* vec=(fruct*)malloc(n*sizeof(fruct));	//vector de n gutui
	for ( i=0; i<n; i++ ){
		fscanf (fin, "%d%d", &vec[i].ht, &vec[i].wt);
		vec[i].niv=((h-vec[i].ht)/u)+1;
		if ( vec[i].niv>maxim )	//calculez nivelul maxim pentru configuratia actuala de gutui
			maxim=vec[i].niv;
	}
	qsort(vec, n, sizeof(fruct), compare);	//sortez gutuile descrescator dupa greutate
	int *level=(int*)malloc((maxim+1)*sizeof(int)); //vector de lungime egala cu nivelul maxim(numarul maxim de gutui ce pot fi culese)
	for ( i=1; i<maxim+1; i++)	//initializarea vectorului cu "vid"(initial toate inaltimile sunt libere)
		level[i]=-1;
	for( i=0; i<n; i++){		//parcurg vectorul de gutui
		if ( vec[i].ht<=h ){
			if ( level[vec[i].niv]==-1 ){	//daca inaltimea corespunzatoare lui e libera,culeg gutuia i
				level[vec[i].niv]=i;
				prada=prada+vec[i].wt;	// in prada caut maximul de gutui pe care le pot culege
				}
			else{
				for ( j=vec[i].niv-1; j>0; j--) //caut un nivel mai mic ( la o inaltime mai mare) care sa fie liber, astfel putand culege gutuia curenta
					if ( level[j]==-1 ){
						level[j]=i;
						prada=prada+vec[i].wt;
						break;
						}
				}
			}
		}
	fprintf(fout,"%d",prada);	//scriu in fisierul de iesire rezultatul
	fclose(fin);
	fclose(fout);
	return 0;
}