Cod sursa(job #465867)

Utilizator radu_voroneanuVoroneanu Radu Stefan radu_voroneanu Data 25 iunie 2010 13:40:44
Problema Minim2 Scor 0
Compilator cpp Status done
Runda Stelele Informaticii 2010, gimnaziu si clasa a IX-a, Ziua 1 Marime 2.65 kb
#include <stdio.h>
#include <algorithm>
#include <string.h>
#define MAXN 100005
#define ERR 0.000001

using namespace std;

inline bool cmp(const float &a, const float &b) { return a>b;}

float P[MAXN], v[MAXN], v2[MAXN];
float A,B;
int i,st,dr,N,mij,sol,ok,j,Rez;
float sum,sum2,S;
int T[MAXN];
int x1,x2,x3;
int Sol, St, Dr, Mij;

int solve(int Y)
{
    memset(v2,0,sizeof(v2));
    memset(T,0,sizeof(T));
    memset(P,0,sizeof(P));

    for (i=1; i<=N; i++) v2[i] = v[i];

    sort(v+1, v+N+1,cmp);

    for (i=1; i<=Y; i++) v[i] *= A;

    sort(v+1, v+N+1, cmp);

    P[0] = 1;
    for (i=1; i<=10000; i++)
        P[i] = P[i-1] * B;

    for (i=1; i<N; i++){
        st=0; dr = 10000; sol = 0;
        while (st<=dr){
            mij = (st+dr)>>1;
            if (v[i]*P[mij] > v[i+1]){
                sol = mij;
                st = mij+1;
            }
            else
                dr = mij-1;
        }
        T[i] = sol;
    }

//    for (i=N; i>=1; --i)
//        T[i] += T[i+1];

    sum = 0;
    for (i=1; i<=N; i++)
        sum += v[i] * P[T[i]];

    while (sum > S+ERR){
        sum *= B;
        T[N]++;
    }

    sum = 0;
    for (i=1; i<=N; i++) sum+=v[i];

    sum2 = sum;
    sum = 0;
    for (i=1; i<=N; i++){
        ok = 0;
        sum2 -= v[i]; sum += v[i];
        for (j=1; j<=T[i]; j++){
            if (sum*B+sum2 < S+ERR) {ok=1; break;}
            sum = sum*B;
        }
        if (ok == 1){
            T[i] = j-1;
            break;
        }
    }
    for (++i; i<=N; ++i) T[i] = 0;

    for (i=N; i>=1; --i) T[i] += T[i+1];

    sum = 0;
    for (i=1; i<=N; i++) sum += v[i]*P[T[i]];

    for (i=1; i<=N; i++)
        if (sum - v[i]*P[T[i]] + v[i]*P[T[i]+1] < S+ERR){
            T[i]++;
            break;
        }
        else{
            sum = sum - v[i]*P[T[i]] + v[i]*P[T[i]+1];
            T[i]++;
        }

    Rez = 0;
    for (i=1; i<=N; i++) Rez += T[i];

    for (i=1; i<=N; i++) v[i] = v2[i];

    return Rez+Y;
}

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

    scanf("%d",&N);
    for (i=1; i<=N; ++i)
        scanf("%f",&v[i]);

    scanf("%f %f %f",&A,&B,&S);

    St=1; Dr = N-1;
    while (St<=Dr){
        Mij = (St+Dr) >> 1;
        x1 = solve(Mij-1);
        x2 = solve(Mij);
        x3 = solve(Mij+1);
        if (x1>=x2 && x2<=x3){
            Sol = Mij;
            break;
        }
        if (x1>=x2) St = Mij+1;
        else Dr = Mij-1;
    }

    if (solve(0) < solve(Sol)) sol = 0;
    if (solve(N) < solve(Sol)) sol = N;

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