Cod sursa(job #635176)

Utilizator sebii_cSebastian Claici sebii_c Data 18 noiembrie 2011 17:28:28
Problema Minim2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <cstdio>
#include <cassert>
#include <queue>
#include <algorithm>

using namespace std;

#define NMAX 100001
#define LgMax 13
#define VMAX 1000000000
#define EPS (1e-6)

int N; double A, B, goal;
int v[NMAX];
double powB[LgMax];

inline pair<int, double> getCount(double limit)
{
	int steps = 0;
	double sum = 0.0;
	vector<double> lastChange;
	for (int i=0; i < N; ++i) {
		if (limit > v[i] * (1 - A) + EPS) {
			sum += v[i];
			continue;	
		}
	
		int curSteps = 1;
		double curVal = v[i] * A;
		
		for (int step = LgMax - 1; step >= 0; --step) {
			if (v[i] * powB[step] * (1 - B) > limit - EPS) {
				curVal *= powB[step];
				curSteps += (1<<step);
			}
		}
		
		if (curVal * (1 - B) > limit - EPS) {
			curVal *= B;
			++curSteps;
		}
		steps += curSteps;
		sum += curVal;
		if (curSteps == 1) {
			lastChange.push_back(v[i] * (1 - A));
		}
		else {
			lastChange.push_back(curVal / B * (1 - B));
		}
	}
	sort(lastChange.begin(), lastChange.end());
	for (size_t k = 0; k < lastChange.size(); ++k) {
		if (sum + lastChange[k] < goal + EPS) {
			sum += lastChange[k];
			--steps;
		}
	}
	return make_pair(steps, sum);
}

inline int isPossible(double limit)
{
	pair<int, double> rez = getCount(limit);
	return rez.second < goal + EPS;
}

int main()
{
	freopen("minim2.in", "r", stdin);
	freopen("minim2.out", "w", stdout);
	scanf("%d", &N);
	
	for (int i = 0; i < N; ++i) {
		scanf("%d", &v[i]);
	}
	scanf("%lf %lf %lf", &A, &B, &goal);
	
	powB[0] = B;
	for (int i = 1; i < LgMax; ++i) {
		powB[i] = powB[i-1] * powB[i-1];
	}
	
	double l = 0, r = VMAX;
	while (r - l > EPS) {
		double m = (l + r) * 0.5;
		if (!isPossible(m)) 
			r = m;
		else 
			l = m;	
	}
	
	pair<int, double> res = getCount(l);
	printf("%d\n", res.first);
	
	return 0;
}