Pagini recente » Cod sursa (job #2655829) | Cod sursa (job #2632655) | Cod sursa (job #2155203) | Cod sursa (job #1582904) | Cod sursa (job #595798)
Cod sursa(job #595798)
# include <fstream>
using namespace std;
ifstream f ("minim2.in");
ofstream g ("minim2.out");
double A[200010];
int n, i, step;
double AB[100010];
double a, b, r, s;
inline int son1 (int dad)
{
return dad << 1;
}
inline int son2 (int dad)
{
return (dad << 1) + 1;
}
void remove_heap (double heap[])
{
int poz = 1;
for (; ; )
{
int s1 = son1 (poz), s2 = son2 (poz), ok = 0;
if (s1 <= n && heap[s1] - heap[s1] * AB[s1] > heap[s2] - heap[s2] * AB[s2] && heap[s1] - heap[s1] * AB[s1] > heap[poz] - heap[poz] * AB[poz])
{
swap (s1, poz);
swap (heap[s1], heap[poz]);
swap (AB[s1], AB[poz]);
ok = 1;
}
else
if (s2 <= n && heap[s2] - heap[s2] * AB[s2] > heap[poz] - heap[poz] * AB[poz])
{
swap (s2, poz);
swap (heap[s2], heap[poz]);
swap (AB[s2], AB[poz]);
ok = 1;
}
if (!ok) break ;
}
}
int main ()
{
f >> n;
for (i = 1; i <= n; ++i)
f >> A[i], s += A[i];
make_heap (A + 1, A + n + 1);
f >> a >> b >> r;
for (i = 1; i <= n; ++i)
AB[i] = a;
while (s >= r)
{
s -= A[1];
s += A[1] * AB[1];
A[1] = A[1] * AB[1];
AB[1] = b;
remove_heap (A);
++step;
}
g << step << '\n';
return 0;
}