Pagini recente » Cod sursa (job #530805) | Cod sursa (job #1422102) | Borderou de evaluare (job #2783306) | Cod sursa (job #341022) | Cod sursa (job #465850)
Cod sursa(job #465850)
#include <stdio.h>
#include <stdlib.h>
float a[100000];
int hp[100000];
char ad[100000];
int n;
float crc=0,rec;
int nr=0;
float na,nb;
inline void lwr(int i, float f)
{
float tmp=a[i];
a[i]*=f;
crc-=tmp-a[i];
nr++;
}
inline int right()
{
return (crc<=rec);
}
inline cst(int i)
{
return (a[hp[i]]-(ad[hp[i]]?a[hp[i]]*na:a[hp[i]]*nb));
}
void heap_up(int i)
{
int pos=i,npos;
while ((pos)&&(cst(pos)>cst(npos=((pos-1)>>1))))
{
hp[pos]=hp[pos]^hp[npos];
hp[npos]=hp[pos]^hp[npos];
hp[pos]=hp[pos]^hp[npos];
pos=npos;
}
}
void heap_down(int i)
{
int pos=i;
while (1)
{
int np1,np2;
np2=(pos+1)<<1;
np1=np2-1;
if (np1>=n)
break;
if (np2!=n)
{
if (cst(np2)>cst(np1))
np1=np2;
}
if (cst(np1)<cst(pos))
break;
hp[pos]=hp[pos]^hp[np1];
hp[np1]=hp[pos]^hp[np1];
hp[pos]=hp[pos]^hp[np1];
pos=np1;
}
}
int main()
{
FILE *fin,*fout;
fin=fopen("minim2.in","r");
fout=fopen("minim2.out","w");
fscanf(fin,"%d",&n);
int i;
for (i=0; i<n; i++)
{
fscanf(fin,"%f",&a[i]);
crc+=a[i];
ad[i]=1;
}
fscanf(fin,"%f %f %f",&na,&nb,&rec);
for (i=0; i<n; i++)
{
hp[i]=i;
heap_up(i);
}
while (!right())
{
if (ad[hp[0]])
{
ad[hp[0]]=0;
lwr(hp[0],na);
}
float max=0;
if ((n>=2)&&(cst(1)>max))
max=cst(1);
if ((n>=3)&&(cst(2)>max))
max=cst(2);
while ((!right())&&(cst(0)>=max))
{
lwr(hp[0],nb);
}
if (right())
break;
heap_down(0);
}
fprintf(fout,"%d\n",nr);
fclose(fin);
fclose(fout);
return 0;
}