Pagini recente » Cod sursa (job #3222662) | Cod sursa (job #1970961) | Cod sursa (job #729132) | Cod sursa (job #3231658) | Cod sursa (job #3152432)
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn=1e5+3;
const int mod=1e9+7;
ifstream fin;
ofstream fout;
ll n;
long double a, b, record, sum=0.0, d[maxn], curr[maxn], curr_sum;
bool first[maxn];
bool moje(int x){
int cnt=0;
long double curr_sum=sum;
for(int i=0; i<n; i++){
curr[i]=d[i];
first[i]=true;
}
for(int i=n-1; i>=0; i--){
if(first[i]){
curr_sum-=curr[i]*(1.0-a);
curr[i]*=a;
first[i]=false;
cnt++;
if(curr_sum<record){
break;
}
}else{
while(curr[i]*(1.0-b) > curr[i-1]*(1.0-a)){
curr_sum-=curr[i]*(1.0-b);
curr[i]*=curr[i]*b;
cnt++;
if(curr_sum<record){
break;
}
}
}
}
return cnt<=x;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
fin.open("minim2.in");
fout.open("minim2.out");
fin>>n;
for(int i=0; i<n; i++){
fin>>d[i];
sum+=d[i];
}
sort(d, d+n);
fin>>a>>b>>record;
ll l=0, r=5e8, m;
while(l!=r-1){
m=(l+r)/2;
if(moje(m)){
r=m;
}else{
l=m;
}
}
fout<<r<<endl;
fin.close();
fout.close();
return 0;
}