Cod sursa(job #465819)

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

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

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)
{
	return val[q]*(1-use[q])<val[w]*(1-use[w]);
}

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;
	in>>n;
	for (i=1;i<=n;i++)
	{
		in>>val[i];
		s+=val[i];
		v[i]=i;
		rec_up(i);
	}
	in>>a>>b>>record;
	for (i=1;i<=n;i++)
		use[i]=a;
	s-=record;
	if (s<=dif)
	{
		out<<"0\n";
		return 0;
	}
	for (nr=0;s>dif;nr++)
	{
		while(!cmp(v[1],v[2]) && s>dif)
		{
			s-=val[v[1]]*(1-use[v[1]]);
			val[v[1]]*=use[v[1]];
			use[v[1]]=b;
			++nr;
		}
		--nr;
		rec_down(1);
	}
	out<<nr<<"\n";
	return 0;
}