Cod sursa(job #1759019)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 18 septembrie 2016 13:18:32
Problema Minim2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.67 kb
#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;
}