Cod sursa(job #595798)

Utilizator vladtarniceruVlad Tarniceru vladtarniceru Data 14 iunie 2011 10:53:24
Problema Minim2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
# include <fstream>
using namespace std;

ifstream f ("minim2.in");
ofstream g ("minim2.out");

double A[200010];
int n, i, step;
double AB[100010];
double a, b, r, s;

inline int son1 (int dad)
{
	return dad << 1;
}

inline int son2 (int dad)
{
	return (dad << 1) + 1;
}

void remove_heap (double heap[])
{
	int poz = 1;
	for (; ; )
	{
		int s1 = son1 (poz), s2 = son2 (poz), ok = 0;
		
		if (s1 <= n && heap[s1] - heap[s1] * AB[s1] > heap[s2] - heap[s2] * AB[s2] && heap[s1] - heap[s1] * AB[s1] > heap[poz] - heap[poz] * AB[poz])
		{
			swap (s1, poz);
			swap (heap[s1], heap[poz]);
			swap (AB[s1], AB[poz]);
			ok = 1;
		}
		else
		if (s2 <= n && heap[s2] - heap[s2] * AB[s2] > heap[poz] - heap[poz] * AB[poz])
		{
			swap (s2, poz);
			swap (heap[s2], heap[poz]);
			swap (AB[s2], AB[poz]);
			ok = 1;
		}
		if (!ok) break ;
	}
}

int main ()
{
	f >> n;
	for (i = 1; i <= n; ++i)
		f >> A[i], s += A[i];
	
	make_heap (A + 1, A + n + 1);
	
	f >> a >> b >> r;
	
	for (i = 1; i <= n; ++i)
		AB[i] = a;
	
	while (s >= r)
	{
		s -= A[1];
		s += A[1] * AB[1];
		A[1] = A[1] * AB[1];
		AB[1] = b;
		remove_heap (A);
		++step;
	}
	
	g << step << '\n';
	
	return 0;
}