Cod sursa(job #3242821)

Utilizator vicvicGriga Victor-Cristian vicvic Data 14 septembrie 2024 11:10:08
Problema Minim2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
using namespace std;
ifstream f ("minim2.in");
ofstream g ("minim2.out");
int n, nr;
double v[1000005], a, b, dist, s, p[1000005], sum;
bool check (double valmx)
{
    sum=nr=0;
    for (int i=1;i<=n;i++)
    {
        double val=v[i];
        if ((1-a)*val>=valmx)
        {
            val*=a;
            nr++;
        }
        if ((1-b)*val>=valmx)
        {
            double aux=val*(1-b);
            int q=(int)(log (valmx/aux)/log (b))+1;
            val*=p[q];
            if (aux*p[q+1]>=valmx)
            {
                q++;
                val*=b;
            }
            nr+=q;
        }
        sum+=val;
    }
    return sum-s<1e-6;
}
int main()
{
    f >> n;
    for (int i=1;i<=n;i++)
    {
        f >> v[i];
        dist+=v[i];
    }
    f >> a >> b >> s;
    p[0]=1;
    for (int i=1;i<=1e4;i++)
    {
        p[i]=p[i-1]*b;
    }
    double st=0, dr=1e9;
    while (dr-st>1e-6)
    {
        double mij = (st+dr)/2;
        if (check (mij)) st=mij;
        else dr=mij;
    }
    check (st);
    for (int i=1;i<=n;i++)
    {
        if (sum+st<=s)
        {
            sum+=st;
            nr--;
        }
    }
    g << nr;
    return 0;
}