Cod sursa(job #465654)

Utilizator S7012MYPetru Trimbitas S7012MY Data 25 iunie 2010 11:11:29
Problema Minim2 Scor 40
Compilator cpp Status done
Runda Stelele Informaticii 2010, gimnaziu si clasa a IX-a, Ziua 1 Marime 0.94 kb
#include <cstdio>
#include <queue>
#include <algorithm>
#define DN 100002
using namespace std;

int main()
{
	priority_queue <double> A;
	priority_queue <double> B;
	int n,i,cont;
	double x,y,z,record,suma=0,a,b;
	freopen("minim2.in","r",stdin);
	freopen("minim2.out","w",stdout);
	scanf("%d",&n);
	for(i=1; i<=n; i++) {
		scanf("%lf",&x);
		suma+=x;
		A.push(x);
	}
	scanf("%lf %lf %lf",&a,&b,&record);
	if(suma<record) printf("0\n");
	else {
		x=A.top();
		A.pop();
		suma-=x;
		x=x*a;
		suma+=x;
		B.push(x);
		for(cont=1; suma>record; cont++) {
			if(!A.empty()) {
				x=A.top();
				y=B.top();
				if(x-(x*a)>y-(y*b)) {
					suma-=x;
					suma+=x*a;
					A.pop();
					B.push(x*a);
				}
				else {
					suma-=y;
					suma+=y*b;
					B.pop();
					B.push(y*b);
				}
			}
			else {
				y=B.top();
				suma-=y;
				suma+=y*b;
				B.pop();
				B.push(y*b);
			}
		}
		printf("%d\n",cont);
	}
	return 0;
}