Cod sursa(job #465904)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 25 iunie 2010 13:55:48
Problema Minim2 Scor 0
Compilator cpp Status done
Runda Stelele Informaticii 2010, gimnaziu si clasa a IX-a, Ziua 1 Marime 1.55 kb
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define nmax 100010
#define e 0.000001

double s, a, b, k, v[nmax];
int n, t, sol;

double put(double n, int p)
{
    double c;
    if (!p) return 1; else
    if (p==1) return n;
    if (!(p%2))
    {
        c=put(n,p/2);
        return c*c;
    } else
    {
        c=put(n,p/2);
        return c*c*n;
    }
}

double search(int s, int d)
{
    int r=0, m;
    double k;
    while (s<d)
    {
        m=(s+d)/2;
        k=put(b, m)*a;
        if (v[0]*k<v[1])
        {
            r=m;
            d=m-1;
        } else s=m+1;
    }
    t=r;
    return put(b,r)*a;
}

int search2(int a, int b)
{
    int r=b, m;
    while (a<b)
    {
        m=(a+b)/2;
        if (v[m]<v[0])
        {
            r=m;
            b=m-1;
        } else a=m+1;
    }
    return r;
}

int cmp(double a, double b)
{
    return a>b;
}

int main()
{

    freopen("minim2.in","r",stdin);
    freopen("minim2.out","w",stdout);
    scanf("%d",&n);
    int i, p;
    double x;
    double c;
    for (i=0; i<n; i++)
    {
        scanf("%lf",&v[i]);
        s+=v[i];
    }
    scanf("%lf %lf %lf",&a,&b,&k);
    sort(v, v+n, cmp);
    while (1)
    {
        if (s<k || (k-s>0 && k-s<e)) break;
        x=search(0,10000);
        c=v[0];
        v[0]*=x;
        s-=c-v[0];
        sol+=t;
        p=search2(1,n-1);
        p--;
        c=v[0];
        for (i=0; i<p; i++) v[i]=v[i+1];
        v[p]=c;
    }
    printf("%d",sol);
}