Cod sursa(job #757873)

Utilizator darrenRares Buhai darren Data 13 iunie 2012 17:46:58
Problema Minim2 Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <cassert>
#include <fstream>
#include <algorithm>

using namespace std;

const double eps = 0.000001;

int N;
double V[100002], powB[10002], S;
double A, B, R;
double rem[100002];

int steps = 0;

int done(double x)
{
	double sum = S;
	int resnow = 0;
	
	int now = 0;
	for (int i = 1; i <= N; ++i)
	{
		double U = V[i];
		
		if (U * (1 - A) >= x)
		{
			sum -= U * (1 - A);
			U *= A;
			++resnow;
			
			int step = 1 << 13, times = -1;
			for (; step; step >>= 1)
			{
				++steps;
				if (times + step <= 10000 && U * powB[times + step] * (1 - B) >= x)
					times += step;
			}
			++times;
			
			if (times != 0)
				rem[++now] = (U * powB[times - 1] * (1 - B)); // cat se sterge ultima data
			sum -= U - U * powB[times];
			U *= powB[times];
			resnow += times;
		}
	}
	
	sort(rem + 1, rem + now + 1);
	for (int i = 1; i <= now; ++i)
		if (sum + rem[i] - R <= eps)
		{
			sum += rem[i];
			--resnow;
		}
	
	if (sum - R <= eps) return resnow;
	return 0;
	
}

int main()
{
	ifstream fin("minim2.in");
	ofstream fout("minim2.out");
	
	fin >> N;
	for (int i = 1; i <= N; ++i)
	{
		fin >> V[i];
		S += V[i];
	}
	fin >> A >> B >> R;
	
	powB[0] = 1;
	for (int i = 1; i <= 10001; ++i)
		powB[i] = powB[i - 1] * B;
	
	if (S - R <= eps)
	{
		fout << 0 << '\n';
		fin.close();
		fout.close();
		return 0;
	}
	
	double l1 = 0, l2 = 1000000000;
	while (l2 - l1 > eps)
	{
		double mid = (l1 + l2) / 2;
		
		if (done(mid)) l1 = mid;
		else           l2 = mid;
	}
	assert(steps <= 70000000);
	fout << done(l1) << '\n';
	
	fin.close();
	fout.close();
}