1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74
| #include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std;
const int MAXN = 100; const char DOUBLE_MIN = 0xc2; const double EPS = 1e-8;
bool bad[MAXN]; int offset[MAXN]; double dp[MAXN][MAXN];
int n, t;
double dfs(int i, int j) { if (dp[i][j] >= 0) return dp[i][j]; if (j == n + 1) return 1; if (i >= t) return 0; dp[i][j] = 0; if (bad[j + 1]) { dp[i][j] += dfs(i + 2, j + 1) / 2; } else { dp[i][j] += dfs(i + 1, j + 1 + offset[j + 1]) / 2; } int to = min(n + 1, j + 2); if (bad[to]) { dp[i][j] += dfs(i + 2, to) / 2; } else { dp[i][j] += dfs(i + 1, to + offset[to]) / 2; } return dp[i][j]; }
int dcmp(double x, double y) { double c = x - y; if (c > EPS) return 1; if (c < -EPS) return -1; return 0; }
int main() { int tcnt; cin >> tcnt; for (int T = 1; T <= tcnt; T++) { cin >> n >> t; memset(bad, false, sizeof bad); memset(offset, 0, sizeof offset); memset(dp, 0xc2, sizeof dp); for (int i = 1; i <= n; i++) { char opr[10]; scanf("%s", opr); if (opr[0] == 'L') { bad[i] = true; } else { offset[i] = floor(atof(opr)); } } double ans = dfs(0, 0); switch(dcmp(ans, 0.5)) { case 1: printf("Bet for. %.4lf\n", ans); break; case 0: printf("Push. %.4lf\n", ans); break; case -1: printf("Bet against. %.4lf\n", ans); break; } } }
|