Pagini recente » Cod sursa (job #2844160) | Cod sursa (job #978553) | Cod sursa (job #2870510) | Cod sursa (job #1468553) | Cod sursa (job #2349301)
#include<bits/stdc++.h>
#define eps 1e-6
#define Nmax 100010
using namespace std;
ifstream f("minim2.in");
ofstream g("minim2.out");
int n;
double dist[Nmax], p[Nmax / 10 + 10], a, b, r;
int itt;
int pz;
bool check(double c)
{
++pz;
double timp = 0.00000;
for(int i = n; i >= 1; --i)
{
int st = 1;
int dr = 10000;
int ans = 0;
if(dist[i] * p[0] - dist[i] * p[1] <= c);
else
if(dist[i] * p[10000] - dist[i] * p[10001] > c)
return 0;
else
while(st <= dr)
{
int mid = (st + dr) / 2;
double diff = dist[i] * p[mid] - dist[i] * p[mid + 1];
if(diff <= c)
ans = mid, dr = mid - 1;
else
st = mid + 1;
}
timp = timp + dist[i] * p[ans];
itt += ans;
if(timp > r)
return 0;
}
return 1;
}
int main()
{
f >> n;
for(int i = 1; i <= n; ++i)
f >> dist[i];
sort(dist + 1, dist + n + 1);
f >> a >> b >> r;
p[0] = 1.0000;
for(int i = 1; i <= 10001; ++i)
p[i] = p[i-1] * b;
double sum = 0;
for(int i = 1; i <= n; ++i)
sum += dist[i];
if(r - sum >= -eps)
{
g << 0;
return 0;
}
dist[n] *= a;
int ans = 0;
sort(dist + 1, dist + n + 1);
double st = 0.0000;
double dr = 500000000.0000;
for(int i = 1; i <= 100; ++i)
{
itt = 0;
double mid = (st + dr) * 0.500000;
if(check(mid))
st = mid, ans = itt;
else
dr = mid;
// g << mid << " " << itt << '\n';
}
g << ans;
return 0;
}