Pagini recente » Cod sursa (job #2632756) | Cod sursa (job #1531944) | Profil Negru_Diana | Monitorul de evaluare | Cod sursa (job #441514)
Cod sursa(job #441514)
#include<stdio.h>
#include<stdlib.h>
typedef struct gut{
int inal, greut;
}gut;
void afisare(gut *a, int n)
{
printf("\n");
int i;
for(i =0; i< n; i++)
printf("%d Inaltime %d, Greutate %d\n", i, a[i].inal,a[i].greut);
}
int compare(const void* x,const void* y)
{
return (((gut*)x)->inal) <= (((gut*)y)->inal);
}
int h,u;
int compare1(const void* x, const void* y)
{
if(((h-(((gut*)x)->inal))/u)!=((h-(((gut*)y)->inal))/u))
if ((((gut*)x)->inal) < (((gut*)y)->inal))
return 1;
else
return -1;
else
return (((gut*)x)->greut) <= (((gut*)y)->greut);
}
int minim(int *c,int n){
int min = c[0];
int i;
for(i = 1; i <n; i++)
if(c[i] < min)
min = c[i];
return min;
}
int main()
{
FILE *f, *fo;
f = fopen("gutui.in", "r");
fo = fopen("gutui.out", "w");
int n, i, j;
gut *a = NULL;
fscanf(f, "%d", &n);
fscanf(f, "%d", &h);
fscanf(f, "%d", &u);
a = (gut*)malloc(n * sizeof(gut));
for(i = 0; i < n; i++)
{
fscanf(f, "%d", &a[i].inal);
fscanf(f, "%d", &a[i].greut);
}
qsort(a, n, sizeof(gut), compare);//ordonare descresc dupa inaltime
// afisare(a,n);
//
//h inaltimea maxima
int *cos;
cos = (int*)malloc(n*sizeof(int));
for(i = 0; i <n; i++)
cos[i] = 0;
int min, nec =0,poz = 0;
while(a[nec].inal > h && nec<n) //daca nu pot fi culese, sar peste ele ca nu ma intereseaza
nec++;
int k = 0;
for(i = nec; i <n; i++) //pornesc de la cate am accesibile, si iau fiecare gutuie
if(a[i].inal <= h) // in caz ca aceasta gutuie e accesibila momentan, o adaug in cos, adica la vectorul de solutii cos
{
cos[k] = a[i].greut;
k++;
for(j = i+1; j <n;j++) //cresc inaltimea tuturor gutuielor cu u(cele urmatoare)
a[j].inal+=u;
}
else //in caz ca gutuia este peste nivel..dar era insa accesbila odata
{
min = cos[0];
for(j = 1; j < k; j++) //calculez minimul dintre ce am cules pana acum
if( cos[j] < min)
{
min = cos[j];
poz = j;
}
// printf("\nMinimul este %d, pe pozitia %d iar gutuia %d\n",min,poz,a[i].greut);
if(a[i].greut > min) //in caz ca gutuia curenta e mai mare decat minimul dintre gutuile culese momentan..o inlocuiesc pe cea minima cu aceasta
cos[poz] = a[i].greut;
}
int s = 0;
for(i =0; i<k; i++) //adun greutatile, si returnez in fisierul de out
{
s += cos[i];
}
fprintf(fo, "%d",s);
free(a);
fclose(f);
fclose(fo);
return 0;
}