Pagini recente » Cod sursa (job #424975) | Cod sursa (job #210150) | Cod sursa (job #2816627) | Cod sursa (job #1687484) | Cod sursa (job #465833)
Cod sursa(job #465833)
#include<stdio.h>
#define infile "minim2.in"
#define outfile "minim2.out"
#define nmax 100010
long v[nmax];
long s[nmax],n;
float a,b,min;
float z[nmax];
long i,sum=0,nr=1,ok=1;
float q,w;
void read()
{
long i;
scanf("%ld",&n);
for(i=1;i<=n;i++)
scanf("%ld",&v[i]);
scanf("%f%f%f",&a,&b,&min);
}
long divide(long p,long q)
{
long st=p,dr=q,x=v[p];
while(st<dr)
{
while(st<dr && v[dr]>=x)
dr--;
v[st]=v[dr];
while(st<dr && v[st]<=x)
st++;
v[dr]=v[st];
}
v[st]=x;
return st;
}
void qs(long p,long q)
{
long m;
m=divide(p,q);
if(m-1 > p)
qs(p,m-1);
if(m+1 < q)
qs(m+1,q);
}
void alpha(long i)
{
long j;
while(((float)v[i]-z[i]-z[i]*b>z[i-1])&&(ok==1))
{
sum+=(float)z[i]*b-z[i];
nr++;
z[i]*=b;
if(sum<min)
{
printf("%ld\n",nr);
ok=0;
}
for(j=i+1;j<=n;j++)
if(z[i]<z[j])
alpha(j);
}
}
void solve()
{
for(i=1;i<=n;i++)
{
sum+=v[i];
z[i]=(float)v[i]*a;
}
for(i=n;i>=1 && ok==1;i--)
{
sum+=z[i]-v[i];
if(sum<min)
{
printf("%ld\n",nr);
ok=0;
}
alpha(i);
}
/*for(i=1;i<=n;i++)
printf("%ld ",v[i]);*/
}
int main()
{
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);
read();
qs(1,n);
solve();
fclose(stdin);
fclose(stdout);
return 0;
}