Cod sursa(job #479276)

Utilizator CezarMocanCezar Mocan CezarMocan Data 23 august 2010 15:18:35
Problema Minim2 Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <cstdio>
#include <algorithm>

const int maxN = 100100;
const int inf = 1000000001;
const long double eps = 1e-12;

using namespace std;

long double A, B, record, powerB[15], finals[maxN];
int N;
int X[maxN], currActions, result, stepsNumber[maxN];

inline void getStepsNumber(long double T) {
	int i, j, current;
	long double currBPower;

	for (i = 1; i <= N; i++) {
		if ((1 - A) * X[i] < T) {
			stepsNumber[i] = 0;
			finals[i] = X[i];
			continue;
		}

		current = 0;
		currBPower = 1;

		for (j = 13; j >= 0; j--) {
			if (X[i] * A * currBPower * powerB[j] * (1 - B) >= T) {
				current += (1 << j);
				currBPower *= powerB[j];
			}
		}

		stepsNumber[i] = current + 2;
		finals[i] = X[i] * A * currBPower * B;

		if (X[i] * A * (1 - B) < T) {
			stepsNumber[i] = 1;
			finals[i] = X[i] * A;
		}

	}
}

inline bool getSolution() {
	long double sumTimes = 0;
	int sumSteps = 0;
	
	for (int i = 1; i <= N; i++) {
		sumTimes += finals[i];
		sumSteps += stepsNumber[i];
	}

	currActions = sumSteps;
	if (sumTimes <= record + eps)
		return true;
	return false;
}

inline void searchSmallestCut(long double left, long double right) {
	long double m;

	while (left <= right) {
		m = (left + right) / 2.0;
		getStepsNumber(m);

		if (getSolution()) {
			result = min(result, currActions);
			left = m + eps;
		}
		else
			right = m - eps;
	}
}


int main() {
	int i, j;
	freopen("minim2.in", "r", stdin);
	freopen("minim2.out", "w", stdout);

	scanf("%d", &N);
	for (i = 1; i <= N; i++)
		scanf("%d", &X[i]);

	scanf("%Lf%Lf%Lf", &A, &B, &record);

	powerB[0] = B;
	for (i = 1; i < 15; i++) 
		powerB[i] = powerB[i - 1] * powerB[i - 1];

	result = inf;
	searchSmallestCut(0, 1000000000);

	printf("%d\n", result);

	return 0;
}