Cod sursa(job #465659)

Utilizator Marius96Marius Gavrilescu Marius96 Data 25 iunie 2010 11:22:22
Problema Minim2 Scor 0
Compilator cpp Status done
Runda Stelele Informaticii 2010, gimnaziu si clasa a IX-a, Ziua 1 Marime 1.56 kb
#include <cstdio>
#include <list>
using namespace std;
float rec,a,b;
class thing{
public:
    float x;
    bool a;
    thing(){
        x=0;a=false;
    }
    thing(float x){
        this->x=x;
    }
};
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);
    float s,x;
    for(int i=0;i<n;i++){
        scanf("%f",&x);
        v.push_back(thing(x));
        s+=x;
    }
    scanf("%f%f%f",&a,&b,&rec);
    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;
            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;
            }
        s-=th1.x;
        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;
}