Cod sursa(job #2259065)

Utilizator ElizaTElla Rose ElizaT Data 12 octombrie 2018 21:57:16
Problema Minim2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include<bits/stdc++.h>

using namespace std;

int n,ans;
int v[100001];
double lgb,x,a,b,r;
double v1[10001];
long double sum;

bool check(double val)
{
    ans = 0;
    sum = 0.0;
    for(int i = 1;i <= n;i++)
    {
        double nr = v[i];
        if((1 - a) * nr >= val)
        {
            nr *= a;
            ans++;
        }
        if((1 - b) * nr >= val)
        {
            double aux = nr * (1 - b);
            int p = (int)(log(val / aux) / lgb) + 1;
            nr = nr * v1[p];
            if(aux * v1[p + 1] >= val)
            {
                p++;
                nr = nr * b;
            }
            ans += p;
        }
        sum += nr;
    }
    return (sum - r < (1e-6));
}
double bs(double st, double dr)
{
    double mj = 0;
    while(dr - st > (1e-6))
    {
        mj = (st + dr) / 2;
        if(check(mj))
            st = mj;
        else
            dr = mj;
    }
    return st;
}
int main()
{
    ifstream fin("minim2.in");
    ofstream fout("minim2.out");
    fin >> n;
    for(int i = 1;i <= n;i++)
        fin >> v[i];
    fin >> a >> b >> r;
    lgb = log(b);
    v1[0] = 1;
    for(int i = 1;i <= 10000;i++)
        v1[i] = v1[i - 1] * b;
    x = bs(0, 1000000000);
    check(x);
    fout << ans - (int)((r - sum) / x) << "\n";
    return 0;
}