Cod sursa(job #465672)

Utilizator ChallengeMurtaza Alexandru Challenge Data 25 iunie 2010 11:43:50
Problema Minim2 Scor 40
Compilator cpp Status done
Runda Stelele Informaticii 2010, gimnaziu si clasa a IX-a, Ziua 1 Marime 2.03 kb
#include <fstream>

using namespace std;

const char InFile[]="minim2.in";
const char OutFile[]="minim2.out";
const int MaxN=100010;
const double EPS=1e-5;

struct s2d{double l,c;};

ifstream fin(InFile);
ofstream fout(OutFile);
double R,x,S,A,B;
s2d heap[MaxN];
int T,N;

inline double h(int nod)
{
    return heap[nod].l-heap[nod].c;
}

inline double dabs(double a)
{
    if(a>0)return a;
    return -a;
}

inline int r(int a)
{
    return a<<1;
}

inline int l(int a)
{
    return (a<<1)+1;
}

inline int f(int a)
{
    return a>>1;
}

void up_heap(int nod)
{
    if(nod<2 || nod>N)return;
    if(h(nod)>h(f(nod)))
    {
        double aux=heap[nod].l;
        heap[nod].l=heap[f(nod)].l;
        heap[f(nod)].l=aux;

        aux=heap[nod].c;
        heap[nod].c=heap[f(nod)].c;
        heap[f(nod)].c=aux;
        up_heap(f(nod));
    }
}

void down_heap(int nod)
{
    if(nod<1 || nod>N)return;

    int i=nod;
    int t=r(nod);
    if(t<=N)
    {
        if(h(t)>h(i))
        {
            i=t;
        }
    }

    t=l(nod);
    if(t<=N)
    {
        if(h(t)>h(i))
        {
            i=t;
        }
    }

    if(i!=nod)
    {
        s2d aux=heap[i];
        heap[i]=heap[nod];
        heap[nod]=aux;
        down_heap(i);
    }
}

void add_heap(double l,double c)
{
    ++heap[0].c;
    heap[(int)(heap[0].c)].l=l;
    heap[(int)(heap[0].c)].c=c;
}

int main()
{
    heap[0].c=0;
    fin>>N;
    for(register int i=0;i<N;++i)
    {
        fin>>x;
        add_heap(x,x);
        S+=x;
    }
    fin>>A>>B>>R;
    for(register int i=1;i<=N;++i)
    {
        heap[i].c*=A;
    }
    for(register int i=1;i<=N;++i)
    {
        up_heap(i);
    }
    for(register int i=1;i<=N;++i)
    {
        down_heap(i);
    }

    fin.close();

    T=0;
    while(R-S<EPS)
    {
        ++T;
        S-=h(1);
        heap[1].l=heap[1].c;
        heap[1].c*=B;
        down_heap(1);
    }

    fout<<T;
    fout.close();
    return 0;
}