Cod sursa(job #616552)

Utilizator fulgerulnegruFMI Ekart Dragos-Ioan fulgerulnegru Data 12 octombrie 2011 20:33:15
Problema Minim2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include<vector>
#include<fstream>
#include<algorithm>
using namespace std;
int main (){
    int n,i,j,mij,nr=0;
    double suma=0;
    double a,b,rec,v2;
    ifstream in ("minim2.in");
    ofstream out ("minim2.out");
    in>>n;
    vector<double> v(n);
    for(i=0;i<n;i++){
        in>>v[i];
        suma+=v[i];
    }
    in>>a>>b>>rec;
    sort(v.begin(),v.end());
    //cautarea binara
    v2=v[n-1];
    v[n-1]*=a;
    suma-=(v2-v[n-1]);
    v2=v[n-1];
    i=0;j=n;
    mij=(i+j)/2;
    while(v[mij]!=v2&&i<j){
        if(v[mij]>v2)
        j=mij-1;
        else
        i=mij+1;
        mij=(i+j)/2;
    }
    for(i=n-1;i>mij;i--)
        v[i]=v[i-1];
    v[mij]=v2;
    nr++;
while(suma>rec){
    v2=v[n-1];
    v[n-1]*=b;
    suma-=(v2-v[n-1]);
    v2=v[n-1];
    i=0;j=n;
    mij=(i+j)/2;
    if(suma<rec)
    break;
    while(v[mij]!=v2&&i<=j){
        if(v[mij]>v2)
        j=mij-1;
        else
        i=mij+1;
        mij=(i+j)/2;
    }
    for(i=n-1;i>mij;i--)
        v[i]=v[i-1];
    v[mij]=v2;
    nr++;
    }
    out<<nr<<" ";
    return 0;
}