Cod sursa(job #465555)

Utilizator mariusdrgdragus marius mariusdrg Data 24 iunie 2010 18:43:28
Problema Minim2 Scor Ascuns
Compilator cpp Status done
Runda Marime 1.79 kb
#include<algorithm>
#include<stdio.h>
#include<math.h>
#include<vector>
#define pb push_back
const int maxn = 100100;
long double eps = 1E-6;

using namespace std;


vector <double> VECT;
long double V[maxn];
long double ALFA,BETA,VAL,RIDIC[210000];
int N;

int ver(long double val)
{
	long double s = 0;
	long double lgb = log(BETA);
	for(int i = 1;i <= N; ++i)
	{
		long double aux = V[i];
		if (aux * (1 - ALFA) >= val)
		{
			aux = aux * ALFA;
			if (aux * (1 - BETA) >= val)
			{
				int nrm = (log(val / aux / (1.0 - BETA))) / lgb;
				aux *= RIDIC[nrm];
				while (aux * (1 - BETA) >= val)
				{
					aux *= BETA;
				}			
			}
		}
		s += aux;
	}
	return s <= VAL;
}

int moves(long double val)
{
	long double s = 0;
	int rasp = 0;	
	long double lgb = log(BETA);
	for(int i = 1;i <= N; ++i)
	{
		long double aux = V[i];
		if (aux * (1 - ALFA) >= val)
		{
			aux = aux * ALFA;
			rasp++;
			if (aux * (1 - BETA) >= val)
			{
				int nrm = (log(val / aux / (1.0 - BETA))) / lgb;
				aux *= RIDIC[nrm];
				rasp += nrm;
				while(aux * (1 - BETA) >= val)
				{
					VECT.pb(aux * (1 - BETA));
					aux *= BETA;
					rasp++;				
				}			
			}
		}
		s += aux;
	}
	sort(VECT.begin(),VECT.end());
	for(int i = 0;i < VECT.size(); ++i)
	{
		if (s + VECT[i] <= VAL)
		{
			s += VECT[i];
			rasp--;
		}
	}
	return rasp;
}


int main()
{
	freopen("minim2.in","r",stdin);
	freopen("minim2.out","w",stdout);
	scanf("%d\n",&N);
	long double dr = 0,st = 0;
	for(int i = 1;i <= N; ++i)
	{
		scanf("%llf ", &V[i]);
		dr = max(dr,(long double)V[i]);
	}	
	scanf("%llf %llf %llf\n",&ALFA,&BETA,&VAL);
	RIDIC[0] = 1;
	for(int i = 1;i <= 200000;++i)
		RIDIC[i] = RIDIC[i - 1] * BETA;	
	while(fabs(dr - st) >= eps)
	{
		long double mid = 0.5 * (st + dr);
		if (ver(mid)) st = mid;
			else dr = mid;
	}	
	printf("%d\n",moves(st));
	return 0;
}