#include #include #include #include //#include #include #include #include #include #include //#include #include #include #include //#include #include #include //#include #include #include #include #include const int dx[] = {1, 0, -1, 0}; const int dy[] = {0, 1, 0, -1}; using namespace std; typedef long long ll; typedef vector vi; typedef vector vll; typedef pair pii; typedef double Real; const int MAX = 11; int P[MAX][MAX], S[MAX][MAX]; int memo[1<<(2*MAX)], rest[MAX]; Real pmemo[MAX][1< que; for (int i = 0; i < C; i++) { rest[i] = tmp%4; tmp /= 4; if (rest[i] == 0) que.push(i); } while (!que.empty()) { int now = que.front(); que.pop(); if (now-1 >= 0) { rest[now-1]--; if (rest[now-1] == 0) que.push(now-1); } if (now+1 < C) { rest[now+1]--; if (rest[now+1] == 0) que.push(now+1); } } int& result = memo[s]; for (int i = 0; i < C; i++) result |= (rest[i]<=0)<>c)&1) prob *= P[r][c]/100.; else prob *= (100-P[r][c])/100.; } } dp[0][0] = 1; for (int r = 0; r < R; r++) { for (int s1 = 0; s1 < (1< check; int origin = 0; for (int i = 0; i < C; i++) { if ((s1>>i)&1) check.push_back(i); else origin |= 3<<(2*i); } for (int s0 = 0; s0 < (1< 0) break; Real prob = dp[r][s0]*pmemo[r][s1]; if (prob == 0) continue; int mask = origin; for (int el : check) { int score = min(3, S[r][el]-((s0>>el)&1)); score = max(0, score); mask |= score<<(2*el); } dp[r+1][memo[mask]] += prob; } } } Real ans = 0; for (int i = 1; i <= R; i++) for (int s = 1; s < (1<