Cod sursa(job #1404991)

Utilizator felixiPuscasu Felix felixi Data 28 martie 2015 18:57:52
Problema Minim2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.38 kb
#include<algorithm>
#include<stdio.h>
#include<math.h>
#include<vector>
#define pb push_back
const int maxn = 100100;
long double eps = 1E-6;

using namespace std;


vector <double> VECT;
long double V[maxn];
long double ALFA,BETA,VAL,RIDIC[21000];
int N;

int ver(long double val)
{
    long double s = 0;
    long double lgb = log(BETA);
    for(int i = 1;i <= N; ++i)
    {
        long double aux = V[i];
        if (aux * (1 - ALFA) >= val)
        {
            aux = aux * ALFA;
            if (aux * (1 - BETA) >= val)
            {
                int nrm = (log(val / aux / (1.0 - BETA))) / lgb;
                aux *= RIDIC[nrm];
                while (aux * (1 - BETA) >= val)
                {
                    aux *= BETA;
                }
            }
        }
        s += aux;
    }
    return fabs(s - VAL) <= eps || s < VAL;
}

int moves(long double val)
{
    long double s = 0;
    int rasp = 0;
    long double lgb = log(BETA);
    for(int i = 1;i <= N; ++i)
    {
        long double aux = V[i];
        if (aux * (1 - ALFA) >= val)
        {
            aux = aux * ALFA;
            rasp++;
            if (aux * (1 - BETA) >= val)
            {
                int nrm = (log(val / aux / (1.0 - BETA))) / lgb;
                aux *= RIDIC[nrm];
                rasp += nrm;
                while(aux * (1 - BETA) >= val)
                {
                    VECT.pb(aux * (1 - BETA));
                    aux *= BETA;
                    rasp++;
                }
            }
        }
        s += aux;
    }
    sort(VECT.begin(),VECT.end());
    for(int i = 0;i < VECT.size(); ++i)
    {
        if (s + VECT[i] <= VAL)
        {
            s += VECT[i];
            rasp--;
        }
    }
    return rasp;
}


int main()
{
    freopen("minim2.in","r",stdin);
    freopen("minim2.out","w",stdout);
    scanf("%d\n",&N);
    long double dr = 0,st = 0;
    for(int i = 1;i <= N; ++i)
    {
        scanf("%llf ", &V[i]);
        dr = max(dr,(long double)V[i]);
    }
    scanf("%llf %llf %llf\n",&ALFA,&BETA,&VAL);
    RIDIC[0] = 1;
    for(int i = 1;i <= 20000;++i)
        RIDIC[i] = RIDIC[i - 1] * BETA;
    while(fabs(dr - st) >= eps)
    {
        long double mid = 0.5 * (st + dr);
        if (ver(mid)) st = mid;
            else dr = mid;
    }
    printf("%d\n",moves(st));
    return 0;
}