Cod sursa(job #1779770)

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