Pagini recente » Cod sursa (job #238530) | Cod sursa (job #1251695) | Cod sursa (job #285442) | Cod sursa (job #2253508) | Cod sursa (job #1404991)
#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;
}