Pagini recente » Cod sursa (job #2052881) | Cod sursa (job #1530075) | Cod sursa (job #2435165) | Cod sursa (job #3178399) | Cod sursa (job #465874)
Cod sursa(job #465874)
#include <stdio.h>
#include <algorithm>
#include <string.h>
#define MAXN 100005
#define ERR 0.000001
using namespace std;
inline bool cmp(const double &a, const double &b) { return a>b;}
double P[MAXN], v[MAXN], v2[MAXN];
double A,B;
int i,st,dr,N,mij,sol,ok,j,Rez;
double sum,sum2,S;
int T[MAXN];
int x1,x2,x3;
int Sol, St, Dr, Mij;
int solve(int Y)
{
memset(v2,0,sizeof(v2));
memset(T,0,sizeof(T));
memset(P,0,sizeof(P));
for (i=1; i<=N; i++) v2[i] = v[i];
sort(v+1, v+N+1,cmp);
for (i=1; i<=Y; i++) v[i] *= A;
sort(v+1, v+N+1, cmp);
P[0] = 1;
for (i=1; i<=10000; i++)
P[i] = P[i-1] * B;
for (i=1; i<N; i++){
st=0; dr = 10000; sol = 0;
while (st<=dr){
mij = (st+dr)>>1;
if (v[i]*P[mij] > v[i+1]){
sol = mij;
st = mij+1;
}
else
dr = mij-1;
}
T[i] = sol;
}
// for (i=N; i>=1; --i)
// T[i] += T[i+1];
sum = 0;
for (i=1; i<=N; i++)
sum += v[i] * P[T[i]];
while (sum > S+ERR){
sum *= B;
T[N]++;
}
sum = 0;
for (i=1; i<=N; i++) sum+=v[i];
sum2 = sum;
sum = 0;
for (i=1; i<=N; i++){
ok = 0;
sum2 -= v[i]; sum += v[i];
for (j=1; j<=T[i]; j++){
if (sum*B+sum2 < S+ERR) {ok=1; break;}
sum = sum*B;
}
if (ok == 1){
T[i] = j-1;
break;
}
}
for (++i; i<=N; ++i) T[i] = 0;
for (i=N; i>=1; --i) T[i] += T[i+1];
sum = 0;
for (i=1; i<=N; i++) sum += v[i]*P[T[i]];
for (i=1; i<=N; i++)
if (sum - v[i]*P[T[i]] + v[i]*P[T[i]+1] < S+ERR){
T[i]++;
break;
}
else{
sum = sum - v[i]*P[T[i]] + v[i]*P[T[i]+1];
T[i]++;
}
Rez = 0;
for (i=1; i<=N; i++) Rez += T[i];
for (i=1; i<=N; i++) v[i] = v2[i];
return Rez+Y;
}
int main()
{
freopen("minim2.in","r",stdin);
freopen("minim2.out","w",stdout);
scanf("%d",&N);
for (i=1; i<=N; ++i)
scanf("%lf",&v[i]);
scanf("%lf %lf %lf",&A,&B,&S);
St=1; Dr = N-1;
while (St<=Dr){
Mij = (St+Dr) >> 1;
x1 = solve(Mij-1);
x2 = solve(Mij);
x3 = solve(Mij+1);
if (x1>=x2 && x2<=x3){
Sol = Mij;
break;
}
if (x1>=x2) St = Mij+1;
else Dr = Mij-1;
}
if (solve(0) < solve(Sol)) sol = 0;
if (solve(N) < solve(Sol)) sol = N;
printf("%d\n", solve(sol));
}