Pagini recente » Cod sursa (job #231185) | Cod sursa (job #2203958) | Cod sursa (job #1930267) | Cod sursa (job #674010) | Cod sursa (job #1219425)
#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;
}