Pagini recente » Borderou de evaluare (job #696057) | Cod sursa (job #2691052) | Cod sursa (job #439074)
Cod sursa(job #439074)
Utilizator |
ana ion ana.ion |
Data |
11 aprilie 2010 12:39:56 |
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;
}