Cod sursa(job #1483170)

Utilizator akaprosAna Kapros akapros Data 8 septembrie 2015 20:50:19
Problema Minim2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.8 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define maxN 100002
#define maxA 10000
#define e 0.000001
using namespace std;
int n, N, i, sol;
double a, b, rec, v[maxN], sum, Pow[maxA];
struct dif
{
    int pos;
    double val;
}x, H[maxN];
int ok(int ac, double x, double y)
{
    if (sum - (x - x * Pow[ac - 1]) < rec || abs(sum - (x - x * Pow[ac - 1])) < e)
        return 0;
    return (x * Pow[ac - 1]) - (x * Pow[ac]) + e > y;
}
int bs(double x, double y)
{
    int i = 0, p = 1 << 13;
    while (p)
    {
        if (i + p <= maxA && ok(i + p, x, y))
            i += p;
        p /= 2;
    }
    return i;
}
inline int father(int nod)
{
    return nod / 2;
}

inline int left_son(int nod)
{
    return nod * 2;
}

inline int right_son(int nod)
{
    return nod * 2 + 1;
}
void sift(int N, int K)
{
    int son;
    do {
        son = 0;

        if (left_son(K) <= N) {
            son = left_son(K);
            if (right_son(K) <= N && H[right_son(K)].val > H[left_son(K)].val) {
                son = right_son(K);
            }
            if (H[son].val <= H[K].val) {
                son = 0;
            }
        }

        if (son) {
            swap(H[K], H[son]);
            K = son;
        }
    } while (son);
}
void percolate (int N, int K)
{
    double key = H[K].val;
    int p = H[K].pos;

    while ((K > 1) && (key > H[father(K)].val)) {
        H[K] = H[father(K)];
        K = father(K);
    }

    H[K].val = key;
    H[K].pos = p;
}
void cut(int& N, int K) {
    H[K] = H[N];
    --N;
    if ((K > 1) && (H[K].val > H[father(K)].val)) {
        percolate(N, K);
    } else {
        sift(N, K);
    }
}
void insert(int& N, dif key)
{
    H[++N] = key;
    percolate(N, N);
}
void read()
{
    freopen("minim2.in", "r", stdin);
    scanf("%d", &n);
    for (i = 1; i <= n; ++ i)
        scanf("%lf", &v[i]),
             sum += v[i];
    scanf("%lf %lf %lf", &a, &b, &rec);
}
void solve()
{
    int i;
    Pow[0] = 1;
    for (i = 1; i <= maxA; ++ i)
        Pow[i] = Pow[i - 1] * b;

    for (i = 1; i <= n; ++ i)
    {
        x.pos = i;
        x.val = (double)(v[i] - (double)(v[i] * a));
        insert(N, x);
    }
    while (sum > rec && abs(sum - rec) > e)
    {
        x = H[1];
        ++ sol;
        cut(N, 1);
        sum -= x.val;
        v[x.pos] -= x.val;
        int p = bs(v[x.pos], H[1].val);
        x.val = v[x.pos] - v[x.pos] * Pow[p];
        sum -= (double)(x.val);
        sol += p;
        v[x.pos] *= Pow[p];
        x.val = v[x.pos] - (v[x.pos] * b);
        insert(N, x);
    }
}
void write()
{
    freopen("minim2.out", "w", stdout);
    printf("%d\n", sol);
}
int main()
{
    read();
    solve();
    write();
    return 0;
}