Cod sursa(job #465906)

Utilizator Marius96Marius Gavrilescu Marius96 Data 25 iunie 2010 13:56:18
Problema Minim2 Scor 0
Compilator cpp Status done
Runda Stelele Informaticii 2010, gimnaziu si clasa a IX-a, Ziua 1 Marime 2.17 kb
#include <cstdio>
#include <list>
#include <cmath>
using namespace std;
double rec,a,b;
class thing{
public:
    double x;
    bool a;
    thing(){
        x=0;a=false;
    }
    thing(double x){
        this->x=x;
        a=false;
    }
};
list<thing> v;
bool comp(thing f1,thing f2){
    return f1.x>f2.x;
}
int main(){
    freopen("minim2.in","r",stdin);
    freopen("minim2.out","w",stdout);
    int n;
    scanf("%d",&n);
    double s=0,x;
    for(int i=0;i<n;i++){
        scanf("%lf",&x);
        v.push_back(thing(x));
        s+=x;
    }
    scanf("%lf%lf%lf",&a,&b,&rec);
    /*long double bvec[14];bvec[0]=1;
    int         pow2[14];pow2[0]=1;
    for(int i=1;i<14;i++){
        bvec[i]=bvec[i-1]*b;
        pow2[i]=pow2[i-1]*2;
    }*/
    v.sort(comp);int ans=0;
    while(s-rec>0||(rec-s>0&&rec-s<0.000001)){
        ans++;
        list<thing>::iterator it=v.begin();
        thing& th1=*it;it++;thing& th2=*it;
        if(!th1.a){
            s-=th1.x;
            /*double fff=pow(a,8192);
            th1.x*=fff;
            while(th1.x<th2.x&&fff>1){
                th1.x/=fff;
                fff=sqrt(fff);
                th1.x*=fff;
            }*/
            th1.x*=a;
            s+=th1.x;
            th1.a=true;
            if(th1.x>th2.x)
                continue;
            v.pop_front();
            while(it->x>th1.x)
                it++;
            v.insert(it,th1);
            continue;
        }
        if(!th2.a)
            if(th2.x-th2.x*a>th1.x-th1.x*b){
                s-=th2.x;
                th2.x*=a;
                s+=th2.x;
                th2.a=true;
                it=v.erase(it);
                while(it->x>th2.x)
                    it++;
                v.insert(it,th2);
                continue;
            }
        //ans--;
        s-=th1.x;
        /*int i=13;
        th1.x*=bvec[i];
        while(th1.x<th2.x&&i>1){
            th1.x/=bvec[i];
            i--;
            th1.x*=bvec[i];
        }
        ans+=pow2[i];*/
        th1.x*=b;
        s+=th1.x;
        if(th1.x>th2.x)
            continue;
            v.pop_front();
        while(it->x>th1.x)
            it++;
        v.insert(it,th1);
    }
    printf("%d",ans);
    return 0;
}