Cod sursa(job #465675)

Utilizator tudgal1001Profir Tudor tudgal1001 Data 25 iunie 2010 11:45:58
Problema Minim2 Scor 0
Compilator cpp Status done
Runda Stelele Informaticii 2010, gimnaziu si clasa a IX-a, Ziua 1 Marime 1.29 kb
#include<cstdio>
#include<algorithm>
#define eps 10e-6
using namespace std;

int v[100002];
float a[100002];

int cmp (int x,int y)
{
    return x>y;
}

int batut (float sum,float rec)
{
    if (rec>=sum && rec-sum>=eps) return 1;
    return 0;
}
int main ()
{
    int n,i,aux,j,rez,poz,cont=0;
    float A,B,rec,sum,dif_max;
    freopen("minim2.in","r",stdin);
    freopen("minim2.out","w",stdout);
    scanf("%d",&n);
    sum=0;
    for (i=1; i<=n; i++)
    {
        scanf("%f",&a[i]);
        sum+=a[i];
    }
    scanf("%f %f",&A,&B);
    scanf("%f",&rec);
    sort(a+1,a+n+1,cmp);
    while (!batut(sum,rec))
    {
        if (v[1]==0)
        {
            v[1]=1;
            sum-=a[1]*(1-A);
            cont++;
            a[1]=a[1]*(1-A);
        }
        else
        {
            dif_max=a[1]*(1-B);
            rez=1;
            poz=2;
            while (v[poz]==1 && poz<n)
            {
                if (a[poz]*(1-B)>dif_max) { dif_max=a[poz]*(1-B); rez=poz; }
                poz++;
            }
            if (a[poz]*(1-A)>dif_max && v[poz]==0) { rez=poz; dif_max=a[poz]*(1-A); }
            v[rez]=1;
            sum-=dif_max;
            cont++;
            a[rez]-=dif_max;
        }
    }
    printf("%d\n",cont);
    return 0;
}