Cod sursa(job #465759)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 25 iunie 2010 12:59:00
Problema Minim2 Scor 0
Compilator cpp Status done
Runda Stelele Informaticii 2010, gimnaziu si clasa a IX-a, Ziua 1 Marime 1.07 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

#define DIM 100005
#define DIF 0.000001
#define MAXACT 2//10000

double V[DIM], W[DIM], CW[DIM];
int N, C, LV, LW;
double A, B, R, S, v, w, dv, dw;

double modul (double a) {
	if (a < 0) a = -a;
	return a;
}

void ord () {
	if (CW[LW]){
		int k = LW;
		double aux;	
		while (W[k - 1] > W[k]){
			aux = W[k], W[k] = W[k - 1], W[k - 1] = aux;
			aux = CW[k], CW[k] = CW[k - 1], CW[k - 1] = aux;
			--k;
		}
	} else --LW;		
}

int main() {
	
	int i;
	freopen ("minim2.in", "r", stdin);
	freopen ("minim2.out", "w", stdout);
	
	scanf ("%d", &N); LV = N;
	for (i = 1; i <= N; scanf("%lf", &V[i]), S += V[i++]);
	scanf ("%lf%lf%lf", &A, &B, &R);
	
	sort (V + 1, V + N + 1);
	
	while (S > R && modul(S - R) > DIF) {
		v = V[LV] * A;
		dv = V[LV] - v;
		w = W[LW] * B;
		dw = W[LW] - w;
		
		if (dv > dw) {
			S -= dv;
			W[++LW] = v;
			--LV;
			CW[LW] = MAXACT - 1;
		} else {
			S -= dw;
			W[LW] = w;
			--CW[LW];
		}
		ord ();
		++C;
	}
	
	printf ("%d", C);
	
	return 0;
}