Cod sursa(job #465685)

Utilizator mihai995mihai995 mihai995 Data 25 iunie 2010 11:51:49
Problema Minim2 Scor 0
Compilator cpp Status done
Runda Stelele Informaticii 2010, gimnaziu si clasa a IX-a, Ziua 1 Marime 1.09 kb
#include <fstream>
using namespace std;

int v[1<<17],n;
double val[1<<17],a,b;
const double dif=0.000001;
bool use[1<<17];

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

inline void sch(int &a,int &b)
{
	int aux;
	aux=a;
	a=b;
	b=aux;
}


inline bool cmp(int q,int w)
{
	double x=a,y=a;
	if (use[q])
		x=b;
	if (use[w])
		y=b;
	return val[q]*(1-x)<val[w]*(1-y);
}

void rec_up(int x)
{
	if (x>1 && val[v[x>>1]]<val[v[x]])
	{
		sch(v[x>>1],v[x]);
		rec_up(x>>1);
	}
}

void rec_down(int x)
{
	int m=x;
	if (cmp(v[m],v[x<<1]) && (x<<1)<=n)
		m<<=1;
	if (cmp(v[m],v[(x<<1)+1]) && (x<<1)<n)
		m=(x<<1)+1;
	if (m!=x)
	{
		sch(v[m],v[x]);
		rec_down(x);
	}
}

int main()
{
	int i,nr;
	double record,s=0,t;
	in>>n;
	for (i=1;i<=n;i++)
	{
		in>>val[i];
		s+=val[i];
		v[i]=i;
		rec_up(i);
	}
	in>>a>>b>>record;
	s-=record;
	if (s<=dif)
	{
		out<<"0\n";
		return 0;
	}
	for (nr=0;s>dif;nr++)
	{
		t=a;
		if (use[v[1]])
			t=b;
		s-=val[v[1]]*(1-t);
		val[v[1]]*=t;
		use[v[1]]=true;
		rec_down(1);
	}
	out<<nr<<"\n";
	return 0;
}