Cod sursa(job #1219429)

Utilizator ZenusTudor Costin Razvan Zenus Data 14 august 2014 10:23:47
Problema Dezastru Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.21 kb
#include <cstdio>
#include <cstring>

using namespace std;

#define NMAX 35

int prime[NMAX],current[NMAX];
double total,f,step;
bool sel[NMAX];
float P[NMAX];
int N,K,i,last;

void descompunere(int X,int sgn)
{
    int f=1;

    while (X>1)
    {
        while (X%prime[f]==0)
        {
            X/=prime[f];
            current[prime[f]]+=sgn;
        }

        ++f;
    }
}

void ciur()
{
    int i,j;
    bool sel[NMAX];

    memset(sel,false,sizeof(sel));

    for (i=2;i<NMAX;++i)
    {
        if (sel[i])
        continue;

        prime[++prime[0]]=i;

        for (j=2*i;j<NMAX;j+=i)
        sel[j]=true;
    }
}

double answer(double total,int N,int K)
{
    ciur();

    int i,j;
    memset(current,0,sizeof(current));

    for (i=1;i<=N;++i)
    descompunere(i,1);

    for (i=1;i<=N-K;++i)
    descompunere(i,-1);

    for (i=1;i<=K;++i)
    descompunere(i,-1);

    for (i=1;i<=N;++i)
    for (j=1;j<=current[i];++j)
    total/=(double)i;

    return total;
}

double dynamic_programming()
{
    double D[NMAX][NMAX];
    int i,j;

    memset(D,0,sizeof(D));

    for (i=0;i<=N;++i)
    D[i][0]=1.0;

    for (i=1;i<=N;++i)
    for (j=1;j<=K;++j)
    D[i][j]=D[i-1][j]+D[i-1][j-1]*P[i];

    return (double)answer(D[N][K],N,K);
}

void back()
{
    int i,current_last;
    double current_f;

    for (i=last+1;i<=N-K+step;++i)
    {
        current_last=last;
        current_f=f;

        if (step<K)
        {
            ++step;
            f*=P[i];
            last=i;

            back();

            --step;
            f=current_f;
            last=current_last;

            continue;
        }

        f*=P[i];
        total+=f;
        f=current_f;
    }
}

double by_back()
{
    int i;
    total=(double)0;

    last=0,f=1.0,step=1;
    back();

    return (double)answer(total,N,K);
}

int main()
{
freopen("dezastru.in","r",stdin);
freopen("dezastru.out","w",stdout);

scanf("%d%d",&N,&K);
for (i=1;i<=N;++i)
scanf("%f",&P[i]);

//100 points by dynamic programming
//printf("%.6lf\n",dynamic_programming());

//?? points by backtracking
printf("%.6lf\n",by_back());

return 0;
}