Pagini recente » Cod sursa (job #1902181) | Cod sursa (job #1010533) | Cod sursa (job #2216373) | Cod sursa (job #2887419) | Cod sursa (job #1759428)
#include <cstdio>
#include <cmath>
#include <algorithm>
#define MAXN 100000
#define MAXP 20000
#define EPS 1e-6
double a, b, k, put[MAXP+1], last[MAXN+1];
int v[MAXN+1], n;
inline void precalc(){
put[0]=1;
for(int i=1; i<=MAXP; i++)
put[i]=put[i-1]*b;
}
inline double calc(double lim){
int r;
double x, sum=0, trans=log(b);
for(int i=1; i<=n; i++){
x=v[i];
if(x*(1-a)>=lim){
x*=a;
if(x*(1-b)>=lim){
r=log(lim/x/(1-b))/trans-2;
if(r<0) r=0;
x*=put[r];
while(x*(1-b)>=lim) x*=b;
}
}
sum+=x;
}
return sum;
}
inline int solve(double lim){
int r, ans=0, k=0;
double x, sum=0, trans=log(b);
for(int i=1; i<=n; i++){
x=v[i];
r=0;
if(x*(1-a)>=lim){
x*=a;
ans++;
if(x*(1-b)>=lim){
r=log(lim/x/(1-b))/trans-2;
if(r<0) r=0;
x*=put[r];
while(x*(1-b)>=lim) x*=b, r++;
if(r>0) last[k++]=(1-b)*(x/b), ans+=r;
}else last[k++]=(1-a)*(x/a);
}
sum+=x;
}
std::sort(last, last+k);
for(int i=0; i<k; i++){
if(sum+last[i]<=k){
sum+=last[i];
ans--;
}
}
return ans;
}
int main(){
int max;
double st, dr, m;
FILE *fin, *fout;
fin=fopen("minim2.in", "r");
fout=fopen("minim2.out", "w");
fscanf(fin, "%d", &n);
for(int i=1; i<=n; i++){
fscanf(fin, "%d", &v[i]);
if(v[i]>max) max=v[i];
}
fscanf(fin, "%lf%lf%lf", &a, &b, &k);
st=0;
dr=max;
precalc();
while(dr-st>=EPS){
m=(st+dr)/2;
if(calc(m)-k<=EPS) st=m;
else dr=m;
}
fprintf(fout, "%d\n", solve(st));
fclose(fin);
fclose(fout);
return 0;
}