Cod sursa(job #673180)

Utilizator repp4raduRadu-Andrei Szasz repp4radu Data 4 februarie 2012 00:33:32
Problema Minim2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <cstdio>
#include <algorithm>

#define MAX 100050

using namespace std;

int v[MAX];
int n;
double s;
double a, b, record;
int nrTrans;

struct number
{
    double toReduce, remain;
    bool transform;
}nr[MAX];

bool cmp(number a, number b)
{
    return a.toReduce < b.toReduce;
}

void citire()
{
    freopen("minim2.in", "r", stdin);
    scanf("%d\n", &n);
    int i;
    for(i = 1; i <= n; i++)
    {
        scanf("%d", &v[i]);
        s += v[i];
    }
    scanf("%lf %lf %lf", &a, &b, &record);
    fclose(stdin);
}

void prepare()
{
    int i;
    for(i = 1; i <= n; i++)
    {
        nr[i].remain = (double)v[i] * a;
        nr[i].toReduce = (double)v[i] * (1 - a);
    }
    sort(nr + 1, nr + n + 1, cmp);
}

void solve()
{
    while(s > record)
    {
        s -= nr[n].toReduce;
        nr[n].toReduce = (1 - b) * nr[n].remain;
        nr[n].remain = b * nr[n].remain;
        nrTrans++;
        sort(nr + 1, nr + n + 1, cmp);
    }
}

void afisare()
{
    freopen("minim2.out", "w", stdout);
    printf("%d", nrTrans);
    fclose(stdout);
}

int main()
{
    citire();
    prepare();
    solve();
    afisare();
    return 0;
}