Pagini recente » Cod sursa (job #1724066) | Cod sursa (job #2049841) | Cod sursa (job #2900743) | Cod sursa (job #167260) | Cod sursa (job #1483170)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define maxN 100002
#define maxA 10000
#define e 0.000001
using namespace std;
int n, N, i, sol;
double a, b, rec, v[maxN], sum, Pow[maxA];
struct dif
{
int pos;
double val;
}x, H[maxN];
int ok(int ac, double x, double y)
{
if (sum - (x - x * Pow[ac - 1]) < rec || abs(sum - (x - x * Pow[ac - 1])) < e)
return 0;
return (x * Pow[ac - 1]) - (x * Pow[ac]) + e > y;
}
int bs(double x, double y)
{
int i = 0, p = 1 << 13;
while (p)
{
if (i + p <= maxA && ok(i + p, x, y))
i += p;
p /= 2;
}
return i;
}
inline int father(int nod)
{
return nod / 2;
}
inline int left_son(int nod)
{
return nod * 2;
}
inline int right_son(int nod)
{
return nod * 2 + 1;
}
void sift(int N, int K)
{
int son;
do {
son = 0;
if (left_son(K) <= N) {
son = left_son(K);
if (right_son(K) <= N && H[right_son(K)].val > H[left_son(K)].val) {
son = right_son(K);
}
if (H[son].val <= H[K].val) {
son = 0;
}
}
if (son) {
swap(H[K], H[son]);
K = son;
}
} while (son);
}
void percolate (int N, int K)
{
double key = H[K].val;
int p = H[K].pos;
while ((K > 1) && (key > H[father(K)].val)) {
H[K] = H[father(K)];
K = father(K);
}
H[K].val = key;
H[K].pos = p;
}
void cut(int& N, int K) {
H[K] = H[N];
--N;
if ((K > 1) && (H[K].val > H[father(K)].val)) {
percolate(N, K);
} else {
sift(N, K);
}
}
void insert(int& N, dif key)
{
H[++N] = key;
percolate(N, N);
}
void read()
{
freopen("minim2.in", "r", stdin);
scanf("%d", &n);
for (i = 1; i <= n; ++ i)
scanf("%lf", &v[i]),
sum += v[i];
scanf("%lf %lf %lf", &a, &b, &rec);
}
void solve()
{
int i;
Pow[0] = 1;
for (i = 1; i <= maxA; ++ i)
Pow[i] = Pow[i - 1] * b;
for (i = 1; i <= n; ++ i)
{
x.pos = i;
x.val = (double)(v[i] - (double)(v[i] * a));
insert(N, x);
}
while (sum > rec && abs(sum - rec) > e)
{
x = H[1];
++ sol;
cut(N, 1);
sum -= x.val;
v[x.pos] -= x.val;
int p = bs(v[x.pos], H[1].val);
x.val = v[x.pos] - v[x.pos] * Pow[p];
sum -= (double)(x.val);
sol += p;
v[x.pos] *= Pow[p];
x.val = v[x.pos] - (v[x.pos] * b);
insert(N, x);
}
}
void write()
{
freopen("minim2.out", "w", stdout);
printf("%d\n", sol);
}
int main()
{
read();
solve();
write();
return 0;
}