Cod sursa(job #516728)

Utilizator vladtarniceruVlad Tarniceru vladtarniceru Data 25 decembrie 2010 23:37:48
Problema Minim2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
# include <fstream>
  using namespace std;
    ifstream f ("minim2.in");
	ofstream g ("minim2.out");
    int n;
	double hip[100100], A, B, rec, s;
	inline bool cmp (double a, double b){
		return a > b;
	}
	inline int son1 (int dad){
		return dad << 1;
	}
	inline int son2 (int dad){
		return (dad << 1) + 1;
	}
	inline void schimba (int &a, int &b){
		int c = a;
		a = b;
		b = c;
	}
	void makeHEAP (){
		int poz = 1;
		for (; ; ){
			int fiu1 = son1 (poz), fiu2 = son2 (poz);
			if (hip[fiu1] >= hip[fiu2] && hip[fiu1] >= hip[poz]){
				double ZZ = hip[fiu1];
				hip[fiu1] = hip[poz];
				hip[poz] = ZZ;
				schimba (fiu1, poz);
			}
			else
			if (hip[fiu1] < hip[fiu2] && hip[fiu2] > hip[poz]){
				double ZZ = hip[fiu2];
				hip[fiu2] = hip[poz];
				hip[poz] = ZZ;
				schimba (fiu2, poz);
			}
			else break ; 
		}
	}
	int main (){
		f >> n;
		for (int i = 1; i <= n; ++i) f >> hip[i], s += hip[i];
		f >> A >> B >> rec;
		sort (hip + 1, hip + n + 1, cmp);
		s -= hip[1];
		hip[1] = hip[1] * A;
		s += hip[1];
		int ps = 1;
		while (s > rec){
			makeHEAP ();
			s -= hip[1];
			hip[1] = hip[1] * B;
			s += hip[1];
			++ps;
		}
		g << ps - 1 << '\n';
		g.close ();
		return 0;
	}