Pagini recente » Borderou de evaluare (job #2022354) | Borderou de evaluare (job #2332010) | Borderou de evaluare (job #2022372) | Borderou de evaluare (job #1589871) | Cod sursa (job #439653)
Cod sursa(job #439653)
#include <stdio.h>
// nr gutui, inaltimea maxima, inaltarea, rezultatul final
long n, hi, u, smax;
// inantimea fiecarei gutui si greutatea
long h[100001], w[100001], i, j, aux, nrs, found, k;
long hmin, h1[100001], w1[100001], imax, max;
void rise()
{
for(i=0; i<n; i++)
h[i]+=u;
}
void update()
{
// nu are sens sa pastram in vectorii h si w valorile pentru fructele care nu mai pot fi accesate (sunt prea sus)
j=0;
for(i=0; i<n; i++)
if(h[i]<=hi)
{
h1[j]=h[i];
w1[j]=w[i];
j++;
}
n=j;
for(i=0; i<n; i++)
{
h[i]=h1[i];
w[i]=w1[i];
}
}
int main()
{
FILE *f=fopen("gutui.in", "r");
FILE *g=fopen("gutui.out", "w");
fscanf(f, "%ld %ld %ld", &n, &hi, &u);
for(i=0; i<n; i++)
fscanf(f, "%ld %ld", &h[i], &w[i]);
//sortam descrescator fructele, in functie de greutate
//trebuie inlocuit cu quicksort, de exemplu
for(i=0; i<n-1; i++)
for(j=i+1; j<n; j++)
if(w[i]<w[j])
{
aux=h[i];
h[i]=h[j];
h[j]=aux;
aux=w[i];
w[i]=w[j];
w[j]=aux;
}
printf("Dupa quicksort, ordonate in functie de inaltime: \n");
for(i=0; i<n; i++)
printf("fructul %ld are inaltimea %ld si greutatea %ld\n", i, h[i], w[i]);
smax=0;
//trebuie la inceput sa elimin valorile prea inalte
update();
/*
hmin=h[n-1];
// printf("hmin este: %ld\n", hmin);
nrs=(hi-hmin)/u+1;
printf("numarul de sectoare este: %ld\n", nrs);
*/
while(n>0)
{
hmin=hi;
for(i=0; i<n; i++)
if(h[i]<hmin)
hmin=h[i];
nrs=(hi-hmin)/u+1;
// printf("numarul de sectoare este: %ld\n", nrs);
// ne intereseaza acum doar primele nrs fructe, in ordinea greutatii, la care ne vom referi ca "fructele grele"
k=0, found=0;
while (found==0) // cautam cel mai inalt fruct care face parte dintre aceste fructe grele
{
k++;
for(i=0; i<nrs; i++)
if(h[i]+k*u>hi && h[i]+(k-1)*u<=hi)
{
found=1;
break;
}
} // k reprezinta stratul pe care am gasit un fruct din cele grele
max=0, imax=-1;
for(i=0; i<nrs; i++) // din fructele grele care se afla pe stratul cel mai de sus, il alegem pe cel mai greu
if(h[i]+k*u>hi && h[i]+(k-1)*u<=hi &&w[i]>max)
{
imax=i;
max=w[i];
}
smax+=max;
for(i=imax+1; i<n; i++) // stergem fructul din vectorii inaltime si greutate
{
h[i-1]=h[i];
w[i-1]=w[i];
}
n--;
rise(); // toate fructele ramase se inalta
update(); // nu ne mai intereseaza fructele inaccesibile
}
printf("%ld\n", smax);
fprintf(g, "%ld", smax);
fclose(f);
fclose(g);
return 0;
}