Cod sursa(job #2005815)

Utilizator akaprosAna Kapros akapros Data 28 iulie 2017 12:07:04
Problema Minim2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.3 kb
#include <bits/stdc++.h>
#define maxN 100002
#define maxM 10002
using namespace std;

FILE *fin = freopen("minim2.in", "r", stdin);
FILE *fout = freopen("minim2.out", "w", stdout);

/* --------------------------------- */
int n;
double v[maxN], a, b, rsum;
/* --------------------------------- */
double sum;
struct Nod
{
    bool ty;
    double x, dif;
    inline bool operator < (const Nod &ot) const
    {
        if (dif == ot.dif)
            return x < ot.x;
        return dif < ot.dif;
    }
};
priority_queue < Nod > H;
/* --------------------------------- */
int ans;
double Pow(int x)
{
    if (x == 0)
        return 1;
    if (x == 1)
        return b;
    if (x & 1)
        return b * Pow(x / 2);
    return Pow(x / 2) * Pow(x / 2);
}
/* --------------------------------- */
int bs(Nod nod, double bstDif)
{
    int i = 0, p = 1 << 13;
    while (p)
    {
        if (i + p < maxM)
        {
            double P = Pow(i + p - 1);
            double lastDif = (nod.x * P - nod.x * P * b), sub = (1.0 - P) * nod.x;
            if (lastDif >= bstDif && sub < (sum - rsum))
                i += p;
        }
        p >>= 1;
    }
    return i;
}
void getAns()
{
    while (sum > rsum && ans < 200000)
    {
        Nod bst = H.top(), sec;
        H.pop();
        sec = H.top();
        if (bst.ty == 0)
        {
            sum -= bst.dif;
            ++ ans;
            bst.ty = 1;
            bst.x *= a;
            bst.dif = (1.0 - b) * bst.x;
        }
        int nrop = bs(bst, sec.dif);
        sum -= bst.x;
        ans += nrop;
        bst.x *= Pow(nrop);
        sum += bst.x;
        H.push({bst.ty, bst.x, bst.x * (1.0 - b)});
    }
}
/* --------------------------------- */
void spCase()
{
    return;
    if (sum <= rsum)
        return ;
    ans = 1;
    sum *= a;
    while (sum > rsum)
    {
        sum *= b;
        ++ ans;
    }

}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i)
    {
        scanf("%lf", &v[i]);
        sum += v[i];
    }
    scanf("%lf%lf%lf", &a, &b, &rsum);
    for (int i = 1; i <= n; ++ i)
        H.push({0, v[i], (1.0 - a) * v[i]});
    //compPow();

    if (n == 1)
        spCase();
    else
        getAns();
    printf("%d\n", ans);
    return 0;
}