SRM 178 Div1 L2

class RandomFA {
    vector<pair<int,int> > parse(string& rule)
    {
        vector<pair<int,int> > ret;
        int ctr=0,a=0,b=0,tmp=0;
        bool state=false;
        while(ctr<rule.size())
        {
            if(rule[ctr]>='0' && rule[ctr]<='9')
            {
                if(!state)
                {
                    a*=10;
                    a+=rule[ctr]-'0';
                }
                else
                {
                    b*=10;
                    b+=rule[ctr]-'0';
                }
            }
            else
            {
                state=!state;
                if(!state)
                {
                    ret.push_back(make_pair(a,b));
                    a=0;b=0;
                }
            }
            ++ctr;
        }
        ret.push_back(make_pair(a,b));
        return ret;
    }
    vector<vector<pair<int,int> > > parseV(vector <string>& rule)
    {
        int n=rule.size();
        vector<vector<pair<int,int> > > ret;
        REP(i,n)
        {
            ret.push_back(parse(rule[i]));
        }
        return ret;
    }
public:
    double getProbability(vector <string> rulesa, vector <string> rulesb, vector <string> rulesc, int finalState, int maxLength)
    {
        int maxState=-1;
        {
            vector<vector<pair<int,int> > > tmp=parseV(rulesa);
            REP(i,tmp.size())
            REP(j,tmp[i].size())
                if(tmp[i][j].first>maxState)
                    maxState=tmp[i][j].first;
            tmp=parseV(rulesb);
            REP(i,tmp.size())
            REP(j,tmp[i].size())
                if(tmp[i][j].first>maxState)
                    maxState=tmp[i][j].first;
            tmp=parseV(rulesc);
            REP(i,tmp.size())
            REP(j,tmp[i].size())
                if(tmp[i][j].first>maxState)
                    maxState=tmp[i][j].first;
        }
        if(finalState==999)
            finalState=maxState+1;
        vector<vector<vector<int> > > v(maxState+2,vector<vector<int> >(maxState+2,vector<int> (3)));
        {
            vector<vector<pair<int,int> > > tmp=parseV(rulesa);
            REP(i,tmp.size())
            REP(j,tmp[i].size())
                v[i][tmp[i][j].first][0]=tmp[i][j].second;
            tmp=parseV(rulesb);
            REP(i,tmp.size())
            REP(j,tmp[i].size())
                v[i][tmp[i][j].first][1]=tmp[i][j].second;
            tmp=parseV(rulesc);
            REP(i,tmp.size())
            REP(j,tmp[i].size())
                v[i][tmp[i][j].first][2]=tmp[i][j].second;
        }
        REP(i,3)
        REP(k,maxState+1)
        {
            int sum=0;

            REP(j,maxState+1)
            {
                sum+=v[k][j][i];
            }
            v[k][maxState+1][i]=100-sum;
        }
        REP(i,3)
            v[maxState+1][maxState+1][i]=100;
        vector<double> dp(maxState+2);
        dp[0]=1;
        int act=0;
        double ssum=1;
        double sum=1;
        REP(i,maxLength)
        {
            sum*=3;
            ssum+=sum;
        }
        double res=0;
        while(act<maxLength)
        {
            vector<double> dp2(maxState+2);
            res+=dp[finalState];
            REP(i,maxState+2)
            REP(k,maxState+2)
            REP(j,3)
            {
                dp2[k]+=(dp[i]*(double)v[i][k][j])/100;
            }
            dp.swap(dp2);
            ++act;
        }
        res+=dp[finalState];
        return res/ssum;
    }

};