Cod sursa(job #465760)

Utilizator andrei.dAndrei Diaconeasa andrei.d Data 25 iunie 2010 12:59:09
Problema Minim2 Scor 0
Compilator cpp Status done
Runda Stelele Informaticii 2010, gimnaziu si clasa a IX-a, Ziua 1 Marime 2.01 kb
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>

using namespace std;

#define file_in "minim2.in"
#define file_out "minim2.out"

#define nmax 101000

int n;
double v[nmax];
double A,B,R;
double suma,sum;
int nr_act;
double minim;
int viz[nmax];


void citire()
{
    freopen(file_in,"r",stdin);
    freopen(file_out,"w",stdout);

    scanf("%d ", &n);
    suma=0;
    for (int i=1;i<=n;++i)
    {
         scanf("%lf", &v[i]);
         suma+=v[i];
    }
    scanf("%lf %lf %lf", &A, &B, &R);
    //printf("%.6lf\n", suma);

}

#define eps 1e-6

int cmp(double x, double y)
{
    if (y-x>eps)
       return 1;
    return 0;
}

void solve()
{
    int i;
    double p;
    int pa=1;
    int nra=0,poz;
    nr_act=0;
    memset(viz,0,sizeof(viz));
    while(cmp(R,suma))
    {
        sum=suma;
        minim=1000000.0;

        //actionez cu A
        nra=0;
        for (i=1;i<=n;++i)
        if (!viz[i])
        {
              sum-=v[i];
              sum+=v[i]*A;
              if (minim>sum)
              {
                  minim=sum;
                  nra++;
                  p=v[i]*A;
                  poz=i;
              }
              sum-=v[i]*A;
              sum+=v[i];
        }

        //actionez cu B
        for (i=1;i<=n;++i)
        {
              sum-=v[i];
              sum+=v[i]*B;
              if (minim>sum)
              {
              //    printf("A intrat\n");
                  minim=sum;
                  p=v[i]*B;
                  nra=0;
                  poz=i;
              }
              //printf("%.6lf %d\n", minim, i);
              sum-=v[i]*B;
              sum+=v[i];
        }
      printf("%.6lf\n", minim);
        suma=minim;
        if (nra!=0) viz[poz]=1;
        v[poz]=p;

        nr_act++;
    }

    printf("%d\n", nr_act);


}

int main()
{
    citire();
    solve();

    fclose(stdin);
    fclose(stdout);

    return 0;
}