Cod sursa(job #465827)

Utilizator deneoAdrian Craciun deneo Data 25 iunie 2010 13:27:51
Problema Minim2 Scor 0
Compilator cpp Status done
Runda Stelele Informaticii 2010, gimnaziu si clasa a IX-a, Ziua 1 Marime 1.01 kb
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int l1, l2;
double v1[100001], v2[100001];
double sum=0, a, b, f;
inline bool equal(float a, float b)
{
	if(abs(a-b)>0.000001)
		return 0;
	else
		return 1;
}
void baga(double val)
{
	for(int i=l2; i>=0; --i)
	{
		if(i==0)
			v2[i]=val;
		else
			if(val>v2[i-1])
				v2[i]=val;
			else
				v2[i]=v2[i-1];
	}
}			
double calc()
{
	double ret;
	if(v1[l1]-v1[l1]*a > v2[l2]-v2[l2]*b)
	{
		ret=v1[l1]-v1[l1]*a;
		++l2;
		baga(v1[l1]*a);
		--l1;
	}
	else
	{
		ret=v2[l2]-v2[l2]*b;
		--l2;
	}
	return ret;
}
		
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);
		v1[i]=aux;
		sum+=aux; 
	}
	sort(v1+1, v1+n+1);
	l1=n; l2=0;
	scanf("%lf%lf%lf", &a, &b, &f);
	while(sum>f || equal(sum, f)) 
	{  
		sum-=calc();  
		++pasi;  
	} 
	printf("%ld\n", pasi); 
	return 0; 
}