Cod sursa(job #1006748)

Utilizator sleepaholicNeculaescu Theodor sleepaholic Data 7 octombrie 2013 17:56:40
Problema Minim2 Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.73 kb
/*
// Sol 1 - 40 p

# include <fstream>
using namespace std;

ifstream f ("minim2.in");
ofstream g ("minim2.out");

double A[200010];
int n, i, step;
double AB[100010];
double a, b, r, s;

inline int son1 (int dad)
{
    return dad << 1;
}

inline int son2 (int dad)
{
    return (dad << 1) + 1;
}

void remove_heap (double heap[])
{
    int poz = 1;
    for (; ; )
    {
        int s1 = son1 (poz), s2 = son2 (poz), ok = 0;

        if (s1 <= n && heap[s1] - heap[s1] * AB[s1] > heap[s2] - heap[s2] * AB[s2] && heap[s1] - heap[s1] * AB[s1] > heap[poz] - heap[poz] * AB[poz])
        {
            swap (s1, poz);
            swap (heap[s1], heap[poz]);
            swap (AB[s1], AB[poz]);
            ok = 1;
        }
        else
        if (s2 <= n && heap[s2] - heap[s2] * AB[s2] > heap[poz] - heap[poz] * AB[poz])
        {
            swap (s2, poz);
            swap (heap[s2], heap[poz]);
            swap (AB[s2], AB[poz]);
            ok = 1;
        }
        if (!ok) break ;
    }
}

int main ()
{
    f >> n;
    for (i = 1; i <= n; ++i)
        f >> A[i], s += A[i];

    make_heap (A + 1, A + n + 1);

    f >> a >> b >> r;

    for (i = 1; i <= n; ++i)
        AB[i] = a;

    while (s >= r)
    {
        s -= A[1];
        s += A[1] * AB[1];
        A[1] = A[1] * AB[1];
        AB[1] = b;
        remove_heap (A);
        ++step;
    }

    g << step << '\n';

    return 0;
}

*/

/* // Sol 2- 70p

#include <fstream>
using namespace std;

ifstream F("minim2.in");
ofstream G("minim2.out");

#define Nmax 100011

int Max;
double A[Nmax];
int Leg[Nmax],Last[Nmax],Poz[Nmax];
double First[Nmax];
int N;
double V,v;
double S;
double T;
int Co;

int pozitionare(int st,int dr)
{
    int xst,xdr;
    xst=0;
    xdr=-1;
    while (st<dr)
        if (A[st]>A[dr])
        {
            st+=xst;
            dr+=xdr;
        }
    else
    {
        swap(A[st],A[dr]);
        xst=1-xst;
        xdr=-1-xdr;
        st+=xst;
        dr+=xdr;
    }
    return st;
}

void quick(int st,int dr)
{
    int p=pozitionare(st,dr);
    if (st<p-1)
        quick(st,p-1);
    if (p+1<dr)
        quick(p+1,dr);
}

int main()
{
    F>>N;
    S=0.0;
    for (int i=1;i<=N;++i)
        F>>A[i],S+=A[i];

    quick(1,N);
    for (int i=1;i<=N;++i)
        Leg[i]=i+1;
    First[0]=1;
    Last[0]=N;
    Poz[0]=1;
    Max=0;

    F>>V>>v;
    V=1-V;v=1-v;

    while (S<T)
    {
        double Sm=First[0]*V;
        int Pm=0;
        for (int i=1;i<=Max;++i)
            if ( Sm<First[i]*v )
                Sm=First[i]*v,Pm=i;

        if (! First[Pm+1])
        {
            Poz[Pm+1]=Poz[Pm];
            First[Pm+1]=Sm;
            Last[Pm+1]=Poz[Pm];
        }
        else
        {
            Leg[Last[Pm+1]]=Poz[Pm];
            Last[Pm+1]=Poz[Leg[Last[Pm+1]]];
        }

        First[Pm]=A[Leg[Poz[Pm]]];
        Poz[Pm]=Leg[Poz[Pm]];
        ++Co;

        S-=Sm;
    }

    G<<Co;

    F.close();
    G.close();
    return 0;
}

*/

// Sol 3 -100p

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define maxn 100010
#define maxp 13
#define eps 0.000001

int n, i, j, k, sol, csol;
double v[maxn], bpt[maxp];
double a, b, r, sum;
vector<double> t;

double reduce(double x, double value)
{
    if(x*(1-a)<value)
        return x;

    if(x*a*(1-b)<value)
    {
        ++csol;
        t.push_back(x*(1-a));
        return x*a;
    }

    x=x*a;
    csol+=2;
    for(int i=maxp-1; i>=0; --i)
        if(x*bpt[i]*(1-b)>=value)
        {
            csol+=(1<<i);
            x*=bpt[i];
        }

    t.push_back(x*(1-b));
    return x*b;
}

int check(double value)
{
    double csum=0;

    t.clear();
    csol=0;
    for(int i=1; i<=n; ++i)
        csum+=reduce(v[i], value);

    sort(t.begin(), t.end());
    for(int i=0; i<t.size(); ++i)
        if(csum+t[i]<r+eps)
        {
            --csol;
            csum+=t[i];
        }
        else
            break;

    if(csum<r+eps)
        return 1;
    return 0;
}

int main()
{
    freopen("minim2.in", "r", stdin);
    freopen("minim2.out", "w", stdout);

    scanf("%d", &n);
    for(int i=1; i<=n; ++i)
        scanf("%lf", &v[i]);

    scanf("%lf%lf%lf", &a, &b, &r);

    bpt[0]=b;
    for(int i=1; i<maxp; ++i)
        bpt[i]=bpt[i-1]*bpt[i-1];

    double left=0, med, right=1000000000;

    sol=1000000000;
    for(int i=1; i<=48; ++i)
    {
        med=(left+right)/2;
        if(check(med))
        {
            sol=min(csol, sol);
            left=med;
        }
        else
            right=med;
    }

    printf("%d\n", sol);
    return 0;
}