Cod sursa(job #2005808)

Utilizator akaprosAna Kapros akapros Data 28 iulie 2017 11:51:36
Problema Minim2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.14 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, Pow[maxN];
struct Nod
{
    bool ty;
    double x, dif;
    bool operator < (const Nod &ot) const
    {
        return dif < ot.dif;
    }
};
priority_queue < Nod > H;
/* --------------------------------- */
int ans;

void compPow()
{
    Pow[0] = 1.0;
    for (int i = 1; i < maxM; ++ i)
        Pow[i] = Pow[i - 1] * b;
}
/* --------------------------------- */
int bs(Nod nod, double bstDif)
{
    int i = 0, p = 1 << 13;
    while (p)
    {
        if (i + p < maxM)
        {
            double lastDif = (nod.x * Pow[i + p - 1] - nod.x * Pow[i + p]), sub = (1.0 - Pow[i + p - 1]) * nod.x;
            if (lastDif >= bstDif && sub < (sum - rsum))
                i += p;
        }
        p >>= 1;
    }
    return i;
}
void getAns()
{
    while (sum > rsum)
    {
        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()
{
    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;
}