//Problem F - Bet or Not (dynamic programming) #include #include void ComputeChances(int,int,int*, double[41][53]); void main() { int n,i,j; double P; char S[5]; int Board[53], t, m; double Chances[41][53]; cin>>n; for(j=0;j>m>>t; Board[0]=Board[m]=Board[m+1]=0; for(i=1;i<=m;i++) { cin>>S; if(S[0]=='L') Board[i]=100; else Board[i]=atoi(S); } ComputeChances(t,m,Board,Chances); P= Chances[t][0]; cout.setf(ios::fixed,ios::floatfield); cout.precision(4); if(P>0.5) cout<<"Bet for. "<< P << endl; else if(P<0.5) cout<<"Bet against. "<< P << endl; else //P=0.5 cout<<"Push. "<< P << endl; } } void ComputeChances(int t, int m, int * Board, double Chances[41][53]) { int i, p, p1,p2,move; // Board[0]=start, Board[m+1]=end double leftchance, rightchance; //do 0 moves for(i=0;i<=m;i++) Chances[0][i]=0; Chances[0][m+1]= Chances[0][m+2]=1; //do 1 moves for(i=0;i<=m-1;i++) { p1=i+1; p2=i+2; if(p1>m) leftchance=1; else if(Board[p1]==100) //lose a turn leftchance=0; else { p1=p1+Board[p1]; leftchance=Chances[0][p1]; } if(p2>m) rightchance=1; else if(Board[p2]==100) //lose a turn rightchance=0; else { p2=p2+Board[p2]; rightchance=Chances[0][p2]; } Chances[1][i]=leftchance/2+rightchance/2; } if(m>2) { if(Board[m]>0 && Board[m]!=100) Chances[1][m-1]=1; else Chances[1][m-1]=0.5; } //do the m-1 and m columns for(i=1;i<=t;i++) Chances[i][m+1]=Chances[i][m]=Chances[i][m+2]=1; //now fill in the rest of the table for(move=2;move<=t;move++) for(p=0;pm) leftchance=1; else if(Board[p1]==100) //lose a turn leftchance=Chances[move-2][p1]; else { p1=p1+Board[p1]; leftchance=Chances[move-1][p1]; } if(p2>m) rightchance=1; else if(Board[p2]==100) //lose a turn rightchance=Chances[move-2][p2]; else { p2=p2+Board[p2]; rightchance=Chances[move-1][p2]; } Chances[move][p]=leftchance/2+rightchance/2; } }