Cod sursa(job #465784)

Utilizator tudgal1001Profir Tudor tudgal1001 Data 25 iunie 2010 13:07:52
Problema Minim2 Scor 0
Compilator cpp Status done
Runda Stelele Informaticii 2010, gimnaziu si clasa a IX-a, Ziua 1 Marime 1.38 kb
#include<cstdio>
#include<algorithm>
#define eps 10e-6
#define ceva -1100000000
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,poz_1,poz_0,caut;
    float A,B,rec,sum,dif_max,max_1,max_0,difmax_1,difmax_0;
    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);
    max_1=ceva; poz_1=0;
    max_0=a[1]; poz_0=1;
    while (!batut(sum,rec))
    {
        if (poz_1==0) difmax_1=ceva;
        else difmax_1=a[poz_1]*(1-B);
        difmax_0=a[poz_0]*(1-A);
        if (difmax_1<difmax_0)
        {
            sum-=difmax_0;
            a[poz_0]-=difmax_0;
            v[poz_0]=1;
            if (a[poz_0]>max_1) { max_1=a[poz_0]; poz_1=poz_0; }
            caut=poz_0+1;
            while (v[caut]==1) caut++;
            max_0=a[caut];
            poz_0=caut;
            cont++;
        }
        else
        {
            sum-=difmax_1;
            a[poz_1]-=difmax_1;
            cont++;
        }
    }
    printf("%d",cont);
    return 0;
}