#include #include /* * Note: * * All probabilities have denominators that are powers of 2, so there * is no need to use rational numbers to represent them precisely (up * to a point...) * */ #define MAX_M 50 #define MAX_T 40 /* should increase this to prevent brute force */ /* 40 should be safe even if we use float to store prob */ #define LOSE_TURN 2*MAX_M /* guaranteed not one of the values */ /* * pad the table to have one more row (for "negative" turns), and * one column for the start, two columns for end */ float prob[MAX_T+2][MAX_M+3]; int m, t; int board[MAX_M+3]; void read_case(void) { char buffer[1024]; int i; scanf("%d %d", &m, &t); for (i = 1; i <= m; i++) { scanf("%s", buffer); if (buffer[0] == 'L') { board[i] = LOSE_TURN; } else { board[i] = atoi(buffer); } } board[0] = board[m+1] = board[m+2] = 0; } void solve_case(void) { int i, j, k, s; /* initialize probabilities for running out of turns */ for (i = 0; i < m+3; i++) { prob[0][i] = prob[1][i] = 0.0; } /* initialize probabilities for being already at the end */ for (i = 1; i <= t+1; i++) { prob[i][m+1] = prob[i][m+2] = 1.0; } /* now do dynamic programming */ for (i = 2; i <= t+1; i++) { for (j = 0; j <= m; j++) { /* go one step */ s = j+1; k = i-1; if (board[s] == LOSE_TURN) { k--; } else { s += board[s]; } prob[i][j] = 0.5 * prob[k][s]; /* go two steps */ s = j+2; k = i-1; if (board[s] == LOSE_TURN) { k--; } else { s += board[s]; } prob[i][j] += 0.5 * prob[k][s]; } } /* print result */ if (prob[t+1][0] < 0.5) { printf("Bet against. %.4f\n", prob[t+1][0]); } else if (prob[t+1][0] == 0.5) { printf("Push. %.4f\n", prob[t+1][0]); } else { printf("Bet for. %.4f\n", prob[t+1][0]); } } int main(void) { int n; scanf("%d", &n); while (n-- > 0) { read_case(); solve_case(); } return 0; }