Cod sursa(job #465810)

Utilizator dicu_dariaDaria Dicu dicu_daria Data 25 iunie 2010 13:17:15
Problema Minim2 Scor 0
Compilator cpp Status done
Runda Stelele Informaticii 2010, gimnaziu si clasa a IX-a, Ziua 1 Marime 1.74 kb
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef struct{
    long double nr,k;
} timpi;
timpi aux,t[100001];
long double urm,total,actionari,a,b,r;
int i,j,n,continua;
bool comp(timpi x,timpi y)
{
    return (x.nr>y.nr);
}

int main()
{
    ifstream fi("minim2.in");
    ofstream fo("minim2.out");
    fi>>n;
    memset(t,0,sizeof(t));
    for(i=1;i<=n;i++){ fi>>t[i].nr; total+=t[i].nr; }
    fi>>a>>b>>r;
    actionari=0;
    sort(t+1,t+n+1,comp);
    for(i=1;i<=n;i++)
    {
        total-=t[i].nr-t[i].nr*a;
        t[i].nr*=a;
        actionari++;
        t[i].k++;
        if(i<n) urm=t[i+1].nr-(t[i+1].nr*a);
        if(i==n) { continua=1; break; }
        while((urm<=(t[i].nr-(t[i].nr*b)))&&(total>r)&&(t[i].k<10000))
        {
            total-=t[i].nr-t[i].nr*b;
            t[i].nr=t[i].nr*b;
            actionari++;
            t[i].k++;
        }
        if(total<=r) break;
    }
    if(continua==1)
    {
        sort(t+1,t+n+1,comp);
        for(i=1;i<=n;i++)
        {
            while(t[i].nr>=t[i+1].nr) {
                                        for(j=1;j<=i;j++)
                                        {
                                        total-=t[j].nr-t[j].nr*b;
                                        t[j].nr=t[j].nr*b;
                                        actionari++;
                                        t[j].k++;
                                        if(total<=r) break;
                                        }
                                        if(total<=r) break;
                                      }
            if(total<=r) break;
            aux=t[i+1];
            t[i+1]=t[i];
            t[i]=aux;

        }



    }
    fo<<actionari<<"\n";
    fo.close();
    return 0;
}