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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
| #include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define red(i, n) for (int i = n - 1; ~i; i--)
const int N = 27 * 27 * 27;
using ll = long long;
struct S {
int x, y;
S() {}
S(int x, int y) : x(x), y(y) {}
bool operator==(const S &b) const { return x == b.x && y == b.y; }
bool operator<(const S &b) const { return x * b.y < y * b.x; }
bool operator<=(const S &b) const { return *this < b || *this == b; }
};
S INF(0, -1), SN[N];
int st[9], nst[9];
auto msk = [&]() {
int t = 0;
red(i, 9) t = t * 3 + nst[i];
return t;
};
auto getmid = [&](S &a, S &b) {
ll down = max(a.y, b.y);
ll up = a.x * (down / a.y) + b.x * (down / b.y);
down <<= 1;
while (up % 2 == 0) up /= 2, down /= 2;
return S(up, down);
};
int Decode(int x) { rep(i, 9) st[i] = x % 3, x /= 3; }
void Init() {
rep(i, N) {
S L = INF, R = INF;
Decode(i);
auto updL = [&]() {
S s = SN[msk()];
if (L == INF || L < s) L = s;
};
auto updR = [&]() {
S s = SN[msk()];
if (R == INF || s < R) R = s;
};
rep(j, 9) if (st[j] == 1) {
int x = j / 3, y = j % 3;
rep(k, 9) nst[k] = st[k];
nst[j] = 0;
if (x) nst[j - 3] = 0;
if (x != 2) nst[j + 3] = 0;
updL();
if (y) nst[j - 1] = 0;
if (y != 2) nst[j + 1] = 0;
updL();
if (x) nst[j - 3] = st[j - 3];
if (x != 2) nst[j + 3] = st[j + 3];
updL();
}
rep(j, 9) if (st[j] == 2) {
int x = j / 3, y = j % 3;
rep(k, 9) nst[k] = st[k];
nst[j] = 0;
updR();
}
if (L == INF && R == INF)
SN[i] = S(0, 1);
else if (L == INF)
SN[i] = S(R.x - 1, 1);
else if (R == INF)
SN[i] = S(L.x + 1, 1);
else {
assert(L < R);
S l = INF, r = INF, x(0, 1);
while (R <= x || x <= L) {
if (R <= x) {
r = x;
if (l == INF)
x.x--;
else
x = getmid(l, r);
} else {
l = x;
if (r == INF)
x.x++;
else
x = getmid(l, r);
}
}
SN[i] = x;
}
}
}
int Tr(char c) {
if (c == 'O') return 1;
if (c == 'X') return 2;
return 0;
}
int T, n;
char s[10];
int main() {
Init();
scanf("%d", &T);
while (T--) {
int sn = 0;
scanf("%d", &n);
while (n--) {
string b;
rep(i, 3) {
scanf("%s", s);
rep(j, 3) b += s[j << 1];
}
int msk = 0;
red(i, 9) msk = msk * 3 + Tr(b[i]);
sn += SN[msk].x * (64 / SN[msk].y);
}
if (sn == 0)
puts("Second");
else if (sn > 0)
puts("Alice");
else
puts("Bob");
}
return 0;
}
|
