/*
    n<=50张卡 如3张：+1 ,-2 , *3  其排列有
    0 + 1 - 2 * 3 = -5
    0 + 1 * 3 - 2 = 1
    0 - 2 + 1 * 3 = 1
    0 - 2 * 3 + 1 = -5
    0 * 3 + 1 - 2 = -1
    0 * 3 - 2 + 1 = -1
    期望为-1.6666666666666667
    求给定的n张卡的期望值

    看解题报告http://www.topcoder.com/wiki/display/tc/TCO'10+Wildcard+Round
    以及bmerry代码的

    不可能n!的枚举
    设+、-卡共有s张
    按照一个+、-卡后接连续的*卡分类，则有s部分，其全排列不影响期望（总共s!种，但期望都一样）
    所以只考虑无序的（无序可以用默认的一种顺序，即卡出现的先后顺序，或者说编号）
    ***a1***a2***  as***
    ***表示*卡
    由于是等概率的，所以总体来统计，每个+、-卡都会接同样的*卡，
    既然每张+、-卡情况一样，那就考虑a1卡
    其后会接0,1,m张*卡
    答案就是 sum * (0,1,m)张*卡的期望   sum = ∑ai 
    求k张*卡的期望可以用dp做
    看bmerry代码的做法，解题报告的麻烦一点吧
    一开始只有s张a卡排着，然后插入一张张*卡
    dp[i,j]表示插入了前面i张*卡，a1后接j张*卡，它们构成的期望值
    分第i张卡插不插入到a1之后构成j张连续的*卡，概率为 该插入的位置/总位置
    dp[i,j] = 
                dp[i-1,j] * (n-j-1)/n
            + m[i]*dp[i-1,j-1] * j/n
    n为s+i

    这道题一个很好的想法就是答案为sum * (0,1,m)张*卡的期望   sum = ∑ai   ！！！！！！
    而求后接k张*卡的期望，bmerry的做法是一张一张卡插入，然后求得期望
    小规模到大规模，通过考虑插入位置来实现，这个做法应该较好
*/
#include<cstdio>
#include<algorithm>
#include<vector>
#include<iostream>
#include<cstring>
#include<string>

using namespace std;

class CalculationCards{

public:

    double getExpected(vector <string> cards){
        vector<int> mults;
        int sum = 0;
        for(vector <string>::iterator it = cards.begin() ; it != cards.end() ; it++){
            string str = *it;
            if(str[0] == '*')
                mults.push_back(str[1]-'0');
            else sum += atoi(str.c_str());
        }

        int m = mults.size() , n = cards.size() - m;
        cout<<m<<" "<<n<<" "<<sum<<endl;

        //dp[i,j]前面i个mul选j个的期望
        double dp[60][60] = {0.0};
        dp[0][0] = 1.0;
        for(int i = 1 ; i <= m ; i++){
            cout<<i<<":\n";
            n++;
            dp[i][0] = dp[i-1][0]*(n-1)/n;
            cout<<dp[i][0];
            for(int j = 1; j <= i ; j++)
            {
                dp[i][j] = 
                    dp[i-1][j]*(n-j-1)/n
                    + mults[i-1]*dp[i-1][j-1]*j/n;
                cout<<" "<<dp[i][j];
            }
            cout<<endl;
        }

        double tot = 0;
        for(int k = 0 ; k <= m ; k++)
            tot += dp[m][k];
        return sum * tot;
    }

};