Cod sursa(job #724375)

Utilizator danalex97Dan H Alexandru danalex97 Data 26 martie 2012 14:51:47
Problema Minim2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.25 kb
/*
// Sol 1 - 40 p

# include <fstream>
using namespace std;

ifstream f ("minim2.in");
ofstream g ("minim2.out");

double A[200010];
int n, i, step;
double AB[100010];
double a, b, r, s;

inline int son1 (int dad)
{
	return dad << 1;
}

inline int son2 (int dad)
{
	return (dad << 1) + 1;
}

void remove_heap (double heap[])
{
	int poz = 1;
	for (; ; )
	{
		int s1 = son1 (poz), s2 = son2 (poz), ok = 0;
		
		if (s1 <= n && heap[s1] - heap[s1] * AB[s1] > heap[s2] - heap[s2] * AB[s2] && heap[s1] - heap[s1] * AB[s1] > heap[poz] - heap[poz] * AB[poz])
		{
			swap (s1, poz);
			swap (heap[s1], heap[poz]);
			swap (AB[s1], AB[poz]);
			ok = 1;
		}
		else
		if (s2 <= n && heap[s2] - heap[s2] * AB[s2] > heap[poz] - heap[poz] * AB[poz])
		{
			swap (s2, poz);
			swap (heap[s2], heap[poz]);
			swap (AB[s2], AB[poz]);
			ok = 1;
		}
		if (!ok) break ;
	}
}

int main ()
{
	f >> n;
	for (i = 1; i <= n; ++i)
		f >> A[i], s += A[i];
	
	make_heap (A + 1, A + n + 1);
	
	f >> a >> b >> r;
	
	for (i = 1; i <= n; ++i)
		AB[i] = a;
	
	while (s >= r)
	{
		s -= A[1];
		s += A[1] * AB[1];
		A[1] = A[1] * AB[1];
		AB[1] = b;
		remove_heap (A);
		++step;
	}
	
	g << step << '\n';
	
	return 0;
}

*/

/* // Sol 2- 70p

#include <fstream>
using namespace std;

ifstream F("minim2.in");
ofstream G("minim2.out");

#define Nmax 100011

int Max;
double A[Nmax];
int Leg[Nmax],Last[Nmax],Poz[Nmax];
double First[Nmax];
int N; 
double V,v;
double S;
double T;
int Co;

int pozitionare(int st,int dr)
{
	int xst,xdr;
	xst=0;
	xdr=-1;
	while (st<dr)
		if (A[st]>A[dr])
		{
			st+=xst;
			dr+=xdr;
		}
	else
	{
        swap(A[st],A[dr]);
        xst=1-xst;
        xdr=-1-xdr;
        st+=xst;
		dr+=xdr;
	}
	return st;
}

void quick(int st,int dr)
{
	int p=pozitionare(st,dr);
	if (st<p-1)
		quick(st,p-1);
	if (p+1<dr)
		quick(p+1,dr);
}

int main()
{
	F>>N;
	S=0.0;
	for (int i=1;i<=N;++i)
		F>>A[i],S+=A[i];	
	
	quick(1,N);
	for (int i=1;i<=N;++i)
		Leg[i]=i+1;
	First[0]=1;
	Last[0]=N;
	Poz[0]=1;
	Max=0;
	
	F>>V>>v;
	V=1-V;v=1-v;
	
	while (S<T)
	{
		double Sm=First[0]*V;
		int Pm=0;
		for (int i=1;i<=Max;++i)
			if ( Sm<First[i]*v )
				Sm=First[i]*v,Pm=i;
		
		if (! First[Pm+1])
		{
			Poz[Pm+1]=Poz[Pm];
			First[Pm+1]=Sm;
			Last[Pm+1]=Poz[Pm];
		}
		else
		{
			Leg[Last[Pm+1]]=Poz[Pm];
			Last[Pm+1]=Poz[Leg[Last[Pm+1]]];
		}
		
		First[Pm]=A[Leg[Poz[Pm]]];
		Poz[Pm]=Leg[Poz[Pm]];
		++Co;
		
		S-=Sm;
	}
	
	G<<Co;
	
	F.close();
	G.close();
	return 0;
}

*/

// Sol 3 -100p

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define maxn 100010
#define maxp 13
#define eps 0.000001

int n, i, j, k, sol, csol;
double v[maxn], bpt[maxp];
double a, b, r, sum;
vector<double> t;

double reduce(double x, double value)
{
    if(x*(1-a)<value)
        return x;

    if(x*a*(1-b)<value)
    {
        ++csol;
        t.push_back(x*(1-a));
        return x*a;
    }

    x=x*a;
    csol+=2;
    for(int i=maxp-1; i>=0; --i)
        if(x*bpt[i]*(1-b)>=value)
        {
            csol+=(1<<i);
            x*=bpt[i];
        }

    t.push_back(x*(1-b));
    return x*b;
}

int check(double value)
{
    double csum=0;

    t.clear();
    csol=0;
    for(int i=1; i<=n; ++i)
        csum+=reduce(v[i], value);

    sort(t.begin(), t.end());
    for(int i=0; i<t.size(); ++i)
        if(csum+t[i]<r+eps)
        {
            --csol;
            csum+=t[i];
        }
        else
            break;

    if(csum<r+eps)
        return 1;
    return 0;
}

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

    scanf("%d", &n);
    for(int i=1; i<=n; ++i)
        scanf("%lf", &v[i]);

    scanf("%lf%lf%lf", &a, &b, &r);

    bpt[0]=b;
    for(int i=1; i<maxp; ++i)
        bpt[i]=bpt[i-1]*bpt[i-1];

    double left=0, med, right=1000000000;

    sol=1000000000;
    for(int i=1; i<=48; ++i)
    {
        med=(left+right)/2;
        if(check(med))
        {
            sol=min(csol, sol);
            left=med;
        }
        else
            right=med;
    }

    printf("%d\n", sol);
    return 0;
}