Cod sursa(job #465864)

Utilizator vladtarniceruVlad Tarniceru vladtarniceru Data 25 iunie 2010 13:39:40
Problema Minim2 Scor 0
Compilator cpp Status done
Runda Stelele Informaticii 2010, gimnaziu si clasa a IX-a, Ziua 1 Marime 1.11 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;
			}
			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]<<' ';
			}
			++action;
		}
		g<<action<<'\n';
		//for(i=1;i<=n;++i) g<<v[i]<<' ';
		g.close();
		return 0;
	}