/*
    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;
    }

};