Cod sursa(job #1219425)

Utilizator ZenusTudor Costin Razvan Zenus Data 14 august 2014 10:12:27
Problema Dezastru Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 kb
#include <cstdio>
#include <cstring>

using namespace std;

#define NMAX 35

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

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 step,int last,double f)
{
    if (step>K)
    {
        total+=f;
        return ;
    }

    for (int i=last+1;i<=N;++i)
    back(step+1,i,f*P[i]);
}

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

    back(1,0,1.0);

    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 : printf("%.6lf\n",dynamic_programming());
printf("%.6lf\n",by_back());

return 0;
}