Pagini recente » Cod sursa (job #2631198) | Cod sursa (job #303107) | Cod sursa (job #333177) | Cod sursa (job #815359) | Cod sursa (job #3238094)
#include <bits/stdc++.h>
using namespace std;
#define int long long
long double eps=1e-10;
const int maxn=100001;
const int mod=1e9+7;
const int logn=25;
int n;
int ar[maxn];
int steps;
long double a,b,r;
long double s[maxn];
long double power[maxn];
long double sum;
int mx=0;
bool f(long double mid)
{
sum=0.0;
for(int i=n-1;i>=0;i--)
{
int l=0;
int r=mx-1;
int m;
int ans=0;
long double cur=s[i];
if(cur-cur*a-mid>=eps)
{
cur*=a;
steps++;
}
while(l<=r)
{
m=(l+r)/2;
long double dif=cur*power[m]-cur*power[m+1];
if(mid-dif>=eps)
{
ans=m;
r=m-1;
}
else
{
l=m+1;
}
}
sum+=cur*power[ans];
steps+=ans;
if(sum-r>eps)return 0;
}
return 1;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
freopen("minim2.in","r",stdin);
freopen("minim2.out","w",stdout);
cin>>n;
for(int i=0;i<n;i++)
{
cin>>ar[i];
}
sort(ar,ar+n);
for(int i=0;i<n;i++)
{
s[i]=ar[i];
}
cin>>a>>b>>r;
power[0]=1.0;
for(int i=1;i<=20000;i++)
{
power[i]=power[i-1]*b;
if(power[i]>eps)
{
mx++;
}
else
{
break;
}
}
long double l=0.0;
long double r=1000000000.0;
long double mid;
long long ans=0;
for(int i=0;i<1000;i++)
{
if(r-l<=eps)break;
steps=0;
mid=(l+r)*0.5;
if(f(mid))
{
l=mid;
ans=steps;
}
else
{
r=mid;
}
}
return 0;
}