Cod sursa(job #465939)

Utilizator cont_de_testeCont Teste cont_de_teste Data 25 iunie 2010 15:27:36
Problema Minim2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include<fstream>
#include<algorithm>
 using namespace std;
 ifstream f("minim2.in");
  ofstream g("minim2.out");
    int n,i,j;
	unsigned long long action=1;
	double s=0,d,a,b,rec,v[100001],i1,i2,dub;
	void trage(int in,int sf){
		int i;
		for(i=sf;i>=in;--i) v[i+1]=v[i];
		v[in]=0;
	}
    int main(){
		f>>n;
		for(i=1;i<=n;++i){
			f>>v[i];
			s+=v[i];
		}
        f>>a>>b>>rec;
		sort(v+1,v+n+1);
		i=n;
		//for(i=1;i<=n;++i) g<<v[i]<<' ';
		i1=v[n]*a;
		s=s-(v[n]-i1);
		v[n]=i1;



	    j=n-1;
		while(v[n]<v[j] && j) --j;
		dub=v[n];
		trage(j+1,n);
		v[j+1]=dub;



		//for(i=1;i<=n;++i) g<<v[i]<<' ';
		while(s>=rec && i>1){
			i1=v[i]*b;
			i2=v[i-1]*b;
			if(i1>i2){
				s=s-(v[i]-i1);
				v[i]=i1; ++action;
			}
			else{
				--i;
				s=s-(v[i]-i2);
				v[i]=i2;



				j=n-1;
    	     	while(v[n]<v[j]) --j;
        		dub=v[n];
              	trage(j+1,n);
        		v[j+1]=dub;

				//g<<'\n';
				//for(i=1;i<=n;++i) g<<v[i]<<' ';
			}

		}
		g<<--action<<'\n';
		//for(i=1;i<=n;++i) g<<v[i]<<' ';
		g.close();
		return 0;
	}