Cod sursa(job #3152431)

Utilizator teo_thrashTeo Stoianov teo_thrash Data 25 septembrie 2023 09:03:55
Problema Minim2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.42 kb
#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]*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;
}