Cod sursa(job #1779757)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 15 octombrie 2016 16:28:26
Problema Dezastru Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include<bits/stdc++.h>
#define maxN 35
using namespace std;
int n,k,nr;
long long l;
double v[maxN],dp[(1<<21)+5],prod,sum,sol;
short digits[(1<<21)+5];
vector<long long> vect;
vector<long long>::iterator it;
bool ok;
int main()
{
    freopen("dezastru.in","r",stdin);
    freopen("dezastru.out","w",stdout);
    scanf("%d%d",&n,&k);
    prod=1.0;
    for(int i=1;i<=n;i++)
    {
        scanf("%lf",&v[i]);
        prod=prod*v[i];
    }
    if((k<<1)>n)
    {
        k=n-k;
        ok=1;
    }
    {
        dp[0]=1.0;
        digits[0]=0;
        l=0;
        for(int i=n-1;i>=(n-k);i--)
        {
            l=l+(1<<i);
        }
        for(long long mask=1;mask<=l;mask++)
        {
            int bit=0;
            while(!(mask & (1<<bit)))
            {
                bit++;
            }
            dp[mask]=dp[mask-(1<<bit)]*v[n-bit];
            digits[mask]=digits[mask-(1<<bit)]+1;
            if(digits[mask]==k)
            {
                vect.push_back(mask);
                nr++;
            }
        }
        sum=0;
        if(!ok)
        {
            for(it=vect.begin();it!=vect.end();it++)
            {
                sum=sum+dp[(*it)];
            }
        }
            else
        {
            for(it=vect.begin();it!=vect.end();it++)
            {
                sum=sum+(prod/dp[(*it)]);
            }
        }
        sol=sum/(1.0*nr);
        printf("%.6lf\n",sol);
    }
    return 0;
}