Cod sursa(job #1249712)

Utilizator tudormaximTudor Maxim tudormaxim Data 27 octombrie 2014 12:54:01
Problema Minim2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.92 kb
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int nmax = 100100;
const double eps = 1e-8;
int n, x[nmax], nract, rez, nrsteps[nmax];
double a, b, record, B[15], fin[nmax];
vector <double> v;
inline void STEPS(double t) {
    int i, j, c;
    double bp;
    for (i=1;i<=n;i++) {
        if ((1-a)*x[i]<t){
            nrsteps[i]=0;
            fin[i]=x[i];
            continue;
        }
        c=0, bp=1;
        for (j=12;j>=0;j--)
            if (x[i] *a*bp*B[j]*(1-b)>=t-eps) {
                c+=(1 << j);
                bp*=B[j];
            }
        nrsteps[i] = c+2;
        fin[i] = x[i]*a*bp*b;
        double update=x[i]*a *bp*(1-b);
        if(x[i]*a*(1-b)<t+eps){
            nrsteps[i] = 1;
            fin[i]=x[i]*a;
            update=x[i]*(1-a);
        }
        v.push_back(update);
    }
}
inline bool SOL() {
    double stimes=0;
    int ssteps=0;
    for (int i=1;i<=n;i++) {
        stimes+=fin[i];
        ssteps+=nrsteps[i];
    }
    sort(v.begin(), v.end());
    for (int i=0;i<(int)v.size();i++)
        if (stimes+v[i]<record+eps) {
            stimes+=v[i];
            ssteps--;
        }
        else break;
    v.clear();
    nract=ssteps;
    if (stimes<=record+eps) return true;
    return false;
}
inline void SEARCH(double left, double right) {
    double m;
    for (int step=1;step<=48;step++) {
        m=(left+right)/2.0;
        STEPS(m);
        if(SOL()){
            rez=min(rez,nract);
            left=m;
        }
        else right=m;
    }
}
int main() {
    freopen("minim2.in", "r", stdin);
    freopen("minim2.out", "w", stdout);
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&x[i]);
    scanf("%lf%lf%lf",&a,&b,&record);
    B[0]=b;
    for (int i=1;i<15;i++)
        B[i]=B[i - 1]*B[i - 1];
    rez=1000000001;
    SEARCH(0,1000000000);
    printf("%d\n", rez);
    return 0;
}