Cod sursa(job #465668)

Utilizator deneoAdrian Craciun deneo Data 25 iunie 2010 11:33:11
Problema Minim2 Scor 0
Compilator cpp Status done
Runda Stelele Informaticii 2010, gimnaziu si clasa a IX-a, Ziua 1 Marime 1.1 kb
#include<cstdio>
#include<set>
#include<cmath>
using namespace std;
bool is[100000];
multiset<double> s1, s2; //s-ar putea sa fie nevoie de double
multiset<double>::iterator it1, it2;
float sum=0, a, b, f;
float calc()
{
	float ret, aux;
	if(!s2.empty())
	{
		it1=s1.end(); it2=s2.end(); // in it2 nu mai putem folosi b;
		it1--; it2--;
		if(*it1-*it1*a > *it2-*it2*b)
		{
			ret=*it1-*it1*a;
			s2.insert(*it1*a);
			s1.erase(it1);
		}
		else
		{
			ret=*it2-*it2*b;
			aux=*it2*b;
			s2.erase(it2);
			s2.insert(aux);
		}
	}
	else
	{
		it1=s1.end();
		it1--;
		ret=*it1-*it1*a;
		s2.insert(*it1*a);
		s1.erase(it1);
	}
	return ret;
}
inline bool equal(float a, float b)
{
	if(abs(a-b)>0.000001)
		return 0;
	else
		return 1;
}

int main()
{
	long n, i, aux, pasi=0;
	freopen("minim2.in", "rt", stdin);
	freopen("minim2.out", "wt", stdout);
	scanf("%ld", &n);
	for(i=1; i<=n; ++i)
	{
		scanf("%ld", &aux);
		s1.insert(aux);
		sum+=aux;
	}
	scanf("%f%f%f", &a, &b, &f);
	while(sum>f && !equal(sum, f)){ sum-=calc(); ++pasi; }
	printf("%ld\n", pasi);
	return 0;
}