Cod sursa(job #520461)

Utilizator capmIonut Vasilescu capm Data 8 ianuarie 2011 19:17:18
Problema Minim2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <stdio.h>

double heap[100010], coef[100010];
double A, B, record, sum;
int n, count;

void buildmaxheap();
void godown(int);
void swap(double&, double&);

int main()
{
	freopen("minim2.in", "r", stdin);
	freopen("minim2.out", "w", stdout);
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i)
	{
		scanf("%lf", &heap[i]);
		sum += heap[i];
	}
	scanf("%lf %lf %lf", &A, &B, &record);
	for(int i = 1; i <= n; ++i)
	{
		coef[i] = A;
	}

	buildmaxheap();

	while(sum > record)
	{
		++count;
		sum -= heap[1] * (1 - coef[1]);
		heap[1] *= coef[1];
		coef[1] = B;
		godown(1);
	}
	printf("%d\n", count);

	return 0;
}

void buildmaxheap()
{
	for(int i = n / 2; i > 0; --i)
	{
		godown(i);
	}
}

void godown(int pos)
{
	int m = pos, l = 2 * pos, r = 2 * pos + 1;
	if(l <= n && heap[l] * (1 - coef[l]) > heap[m] * (1 - coef[m])) m = l;
	if(r <= n && heap[r] * (1 - coef[r]) > heap[m] * (1 - coef[m])) m = r;
	if(pos != m)
	{
		swap(heap[pos], heap[m]);
		swap(coef[pos], coef[m]);
		godown(m);
	}
}

inline void swap(double&a, double&b)
{
	double temp = a;
	a = b;
	b = temp;
}