Pagini recente » Cod sursa (job #1023808) | Cod sursa (job #1113658) | Cod sursa (job #2044109) | Cod sursa (job #2727949) | Cod sursa (job #1759019)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
class InputReader {
public:
InputReader() {}
InputReader(const char *file_name) {
input_file = fopen(file_name, "r");
cursor = 0;
fread(buffer, SIZE, 1, input_file);
}
inline InputReader &operator >>(int &n) {
while(buffer[cursor] < '0' || buffer[cursor] > '9') {
advance();
}
n = 0;
while('0' <= buffer[cursor] && buffer[cursor] <= '9') {
n = n * 10 + buffer[cursor] - '0';
advance();
}
return *this;
}
inline InputReader &operator >>(double &x) {
int a = 0, b = 0;
double power = 1;
while(buffer[cursor] < '0' || buffer[cursor] > '9') {
advance();
}
while('0' <= buffer[cursor] && buffer[cursor] <= '9') {
a = a * 10 + buffer[cursor] - '0';
advance();
}
if (buffer[cursor] != '.') {
x = a;
return *this;
}
while(buffer[cursor] < '0' || buffer[cursor] > '9') {
advance();
}
while('0' <= buffer[cursor] && buffer[cursor] <= '9') {
b = b * 10 + buffer[cursor] - '0';
power /= 10.0;
advance();
}
x = a + power * b;
return *this;
}
private:
FILE *input_file;
static const int SIZE = 1 << 17;
int cursor;
char buffer[SIZE];
inline void advance() {
++ cursor;
if(cursor == SIZE) {
cursor = 0;
fread(buffer, SIZE, 1, input_file);
}
}
};
InputReader cin("minim2.in");
ofstream cout("minim2.out");
const int MAXN = 100000;
const int MAXP = 13;
const double EPS = 1e-6;
const int INF = 1000000000;
double v[1 + MAXN];
double power[MAXP];
int n, current;
double a, b, limit;
vector<double> temp;
double Reduce(double x, double value) {
if (x * (1 - a) < value)
return x;
if (x * a * (1 - b) < value) {
current++;
temp.push_back(x * (1 - a));
return x * a;
}
x *= a;
current += 2;
for (int i = MAXP - 1; i >= 0; i--)
if (x * power[i] * (1 - b) >= value) {
current += (1 << i);
x *= power[i];
}
temp.push_back(x * (1 - b));
return x * b;
}
bool Check(double value) {
temp.clear();
double sum = 0;
current = 0;
for (int i = 1; i <= n; i++)
sum += Reduce(v[i], value);
sort(temp.begin(), temp.end());
for (auto &it : temp)
if (sum + it < limit + EPS) {
current--;
sum += it;
}
else
break;
if (sum < limit + EPS)
return true;
return false;
}
int BinarySearch() {
double left = 0, right = INF;
int answer = INF;
for (int step = 1; step <= 48; step++) {
double middle = (left + right) / 2;
if (Check(middle)) {
answer = min(answer, current);
left = middle;
}
else
right = middle;
}
return answer;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
v[i] = x;
}
cin >> a >> b >> limit;
power[0] = b;
for (int i = 1; i < MAXP; i++)
power[i] = power[i - 1] * power[i - 1];
cout << BinarySearch() << "\n";
return 0;
}