Pagini recente » Cod sursa (job #463178) | Cod sursa (job #2107826) | Cod sursa (job #2812670) | Cod sursa (job #487432) | Cod sursa (job #463575)
Cod sursa(job #463575)
//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;
}