Cod sursa(job #3242817)

Utilizator vicvicGriga Victor-Cristian vicvic Data 14 septembrie 2024 10:59:45
Problema Minim2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
ifstream f ("minim2.in");
ofstream g ("minim2.out");
int n, nr;
double v[1000005], a, b, dist, s, p[100005], sum;
bool check (double valmx)
{
    sum=nr=0;
    for (int i=1;i<=n;i++)
    {
        if (v[i]*(1-a)<valmx)
        {
            sum+=v[i];
        }
        else if (v[i]*a*(1-b)<valmx)
        {
            sum+=v[i]*a;
            nr++;
        }
        else
        {
            nr++;
            double va=v[i]*a*(1-b);
            int q=(int)(log (valmx/va)/log (b));
            if (va*p[q+1]>=valmx)
            {
                q++;
            }
            nr+=q;
            sum+=v[i]*a*p[q];
        }
    }
    return abs (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;
}