#include #include #include #include #include #include #include #include #include using namespace std; #pragma warning (disable: 4996) // 入力 int N; double P, Q, R; string S; // その他の変数 int dep[1 << 20]; bool tonari[1 << 20]; vector V1[1 << 19]; vector V2[1 << 19]; vector V3[1 << 19]; double dfs(int cl, int cr) { int CurrentDep = dep[cl]; // OR の計算 int pos1 = lower_bound(V1[CurrentDep].begin(), V1[CurrentDep].end(), cl + 0) - V1[CurrentDep].begin(); int pos2 = lower_bound(V1[CurrentDep].begin(), V1[CurrentDep].end(), cr + 1) - V1[CurrentDep].begin(); if (pos1 < pos2) { int border = V1[CurrentDep][pos2 - 1]; double v1 = dfs(cl, border - 1); double v2 = dfs(border + 2, cr); double t = 1.0 - (1.0 - v1) * (1.0 - v2); double u = (1.0 - t) * R + t * (1.0 - R); return u; } // AND の計算 int pos3 = lower_bound(V2[CurrentDep].begin(), V2[CurrentDep].end(), cl + 0) - V2[CurrentDep].begin(); int pos4 = lower_bound(V2[CurrentDep].begin(), V2[CurrentDep].end(), cr + 1) - V2[CurrentDep].begin(); if (pos3 < pos4) { int border = V2[CurrentDep][pos4 - 1]; double v1 = dfs(cl, border - 1); double v2 = dfs(border + 3, cr); double t = v1 * v2; double u = (1.0 - t) * R + t * (1.0 - R); return u; } // RANDOM の計算 if (cr - cl >= 6 && S[cl] == 'r') { int pos5 = lower_bound(V3[CurrentDep + 1].begin(), V3[CurrentDep + 1].end(), cl + 7) - V3[CurrentDep + 1].begin(); int pos6 = lower_bound(V3[CurrentDep + 1].begin(), V3[CurrentDep + 1].end(), cr + 0) - V3[CurrentDep + 1].begin(); int border = V3[CurrentDep + 1][pos5]; double v1 = dfs(cl + 7, border - 1); double v2 = dfs(border, cr - 1); double u = v1 * v2 * P + (1.0 - v1 * v2) * Q; return u; } // (...) の場合 if (S[cl] == '(' && S[cr] == ')') { return dfs(cl + 1, cr - 1); } // それ以外の場合 if (cr - cl == 2 && S[cl] == 'Y') { return 1.0; } if (cr - cl == 1 && S[cl] == 'N') { return 0.0; } return 869120.0; } int main() { // Step #1. 入力 cin >> N >> P >> Q >> R; cin >> S; // Step #2. 前処理 for (int i = 0; i < S.size(); i++) { dep[i + 1] = dep[i]; if (S[i] == '(') dep[i + 1] = dep[i] + 1; if (S[i] == ')') dep[i + 1] = dep[i] - 1; } int cx = 0; while (cx < S.size()) { bool flag = true; if (S[cx] == 'r') { cx += 6; flag = false; } else if (S[cx] == 'o') { V1[dep[cx]].push_back(cx); cx += 2; flag = false; } else if (S[cx] == 'a') { V2[dep[cx]].push_back(cx); cx += 3; flag = false; } else if (cx + 1 < (int)S.size()) { int cnt = 0; if (S[cx + 0] == 'S' || S[cx + 0] == 'O' || S[cx + 0] == ')') cnt += 1; if (S[cx + 1] == 'Y' || S[cx + 1] == 'N' || S[cx + 1] == 'r' || S[cx + 1] == '(') cnt += 1; if (cnt == 2) tonari[cx + 1] = true; } if (tonari[cx + 1] == true) V3[dep[cx + 1]].push_back(cx + 1); if (flag == true) cx += 1; } // Step #3. 構文解析 double I = dfs(0, N - 1); int J = (int)(100.0 * I); cout << J << endl; return 0; }