結果
問題 | No.2814 Block Game |
ユーザー |
|
提出日時 | 2024-07-20 00:38:49 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 21,312 bytes |
コンパイル時間 | 5,257 ms |
コンパイル使用メモリ | 291,696 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-20 00:39:13 |
合計ジャッジ時間 | 22,849 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | WA * 20 |
ソースコード
#ifndef HIDDEN_IN_VS // 折りたたみ用// 警告の抑制#define _CRT_SECURE_NO_WARNINGS// ライブラリの読み込み#include <bits/stdc++.h>using namespace std;// 型名の短縮using ll = long long; using ull = unsigned long long; // -2^63 ~ 2^63 = 9 * 10^18(int は -2^31 ~ 2^31 = 2 * 10^9)using pii = pair<int, int>; using pll = pair<ll, ll>; using pil = pair<int, ll>; using pli = pair<ll, int>;using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>; using vvvvi = vector<vvvi>;using vl = vector<ll>; using vvl = vector<vl>; using vvvl = vector<vvl>; using vvvvl = vector<vvvl>;using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;using vc = vector<char>; using vvc = vector<vc>; using vvvc = vector<vvc>;using vd = vector<double>; using vvd = vector<vd>; using vvvd = vector<vvd>;template <class T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;using Graph = vvi;// 定数の定義const double PI = acos(-1);int DX[4] = { 1, 0, -1, 0 }; // 4 近傍(下,右,上,左)int DY[4] = { 0, 1, 0, -1 };int INF = 1001001001; ll INFL = 4004004003094073385LL; // (int)INFL = INF, (int)(-INFL) = -INF;// 入出力高速化struct fast_io { fast_io() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(18); } } fastIOtmp;// 汎用マクロの定義#define all(a) (a).begin(), (a).end()#define sz(x) ((int)(x).size())#define lbpos(a, x) (int)distance((a).begin(), std::lower_bound(all(a), x))#define ubpos(a, x) (int)distance((a).begin(), std::upper_bound(all(a), x))#define Yes(b) {cout << ((b) ? "Yes\n" : "No\n");}#define rep(i, n) for(int i = 0, i##_len = int(n); i < i##_len; ++i) // 0 から n-1 まで昇順#define repi(i, s, t) for(int i = int(s), i##_end = int(t); i <= i##_end; ++i) // s から t まで昇順#define repir(i, s, t) for(int i = int(s), i##_end = int(t); i >= i##_end; --i) // s から t まで降順#define repe(v, a) for(const auto& v : (a)) // a の全要素(変更不可能)#define repea(v, a) for(auto& v : (a)) // a の全要素(変更可能)#define repb(set, d) for(int set = 0, set##_ub = 1 << int(d); set < set##_ub; ++set) // d ビット全探索(昇順)#define repis(i, set) for(int i = lsb(set), bset##i = set; i < 32; bset##i -= 1 << i, i = lsb(bset##i)) // set の全要素(昇順)#define repp(a) sort(all(a)); for(bool a##_perm = true; a##_perm; a##_perm = next_permutation(all(a))) // a の順列全て(昇順)#define uniq(a) {sort(all(a)); (a).erase(unique(all(a)), (a).end());} // 重複除去#define EXIT(a) {cout << (a) << endl; exit(0);} // 強制終了#define inQ(x, y, u, l, d, r) ((u) <= (x) && (l) <= (y) && (x) < (d) && (y) < (r)) // 半開矩形内判定// 汎用関数の定義template <class T> inline ll powi(T n, int k) { ll v = 1; rep(i, k) v *= n; return v; }template <class T> inline bool chmax(T& M, const T& x) { if (M < x) { M = x; return true; } return false; } // 最大値を更新(更新されたら trueを返す)template <class T> inline bool chmin(T& m, const T& x) { if (m > x) { m = x; return true; } return false; } // 最小値を更新(更新されたら trueを返す)template <class T> inline T getb(T set, int i) { return (set >> i) & T(1); }template <class T> inline T smod(T n, T m) { n %= m; if (n < 0) n += m; return n; } // 非負mod// 演算子オーバーロードtemplate <class T, class U> inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }template <class T> inline istream& operator>>(istream& is, vector<T>& v) { repea(x, v) is >> x; return is; }template <class T> inline vector<T>& operator--(vector<T>& v) { repea(x, v) --x; return v; }template <class T> inline vector<T>& operator++(vector<T>& v) { repea(x, v) ++x; return v; }#endif // 折りたたみ用#if __has_include(<atcoder/all>)#include <atcoder/all>using namespace atcoder;#ifdef _MSC_VER#include "localACL.hpp"#endif//using mint = modint1000000007;using mint = modint998244353;//using mint = static_modint<1000000000>;//using mint = modint; // mint::set_mod(m);namespace atcoder {inline istream& operator>>(istream& is, mint& x) { ll x_; is >> x_; x = x_; return is; }inline ostream& operator<<(ostream& os, const mint& x) { os << x.val(); return os; }}using vm = vector<mint>; using vvm = vector<vm>; using vvvm = vector<vvm>; using vvvvm = vector<vvvm>; using pim = pair<int, mint>;#endif#ifdef _MSC_VER // 手元環境(Visual Studio)#include "local.hpp"#else // 提出用(gcc)inline int popcount(int n) { return __builtin_popcount(n); }inline int popcount(ll n) { return __builtin_popcountll(n); }inline int lsb(int n) { return n != 0 ? __builtin_ctz(n) : 32; }inline int lsb(ll n) { return n != 0 ? __builtin_ctzll(n) : 64; }template <size_t N> inline int lsb(const bitset<N>& b) { return b._Find_first(); }inline int msb(int n) { return n != 0 ? (31 - __builtin_clz(n)) : -1; }inline int msb(ll n) { return n != 0 ? (63 - __builtin_clzll(n)) : -1; }#define dump(...)#define dumpel(v)#define dump_list(v)#define dump_mat(v)#define input_from_file(f)#define output_to_file(f)#define Assert(b) { if (!(b)) { vc MLE(1<<30); EXIT(MLE.back()); } } // RE の代わりに MLE を出す#endifvoid WA() {int t;cin >> t;rep(hoge, t) {ll n; string s;cin >> n >> s;if (n == 1) {cout << (s == "Odd" ? "Alice" : "Bob") << "\n";}else if (n == 2) {cout << (s == "Odd" ? "Alice" : "Bob") << "\n";}else if (popcount(n) == 1) {cout << (s == "Even" ? "Alice" : "Bob") << "\n";}else if (n % 2 == 0) {ll m = n / 2;cout << ((s == "Even") == (m % 2 == 0) ? "Bob" : "Alice") << "\n";}else {ll m = (n - 1) / 2;int b = ((n - 1) & m) == m;dump(n, m, b);cout << ((s == "Even") == (b % 2 == 0) ? "Alice" : "Bob") << "\n";}}}//【形式的冪級数(F_2)】/** BFPS<N>() : O(1)* 零多項式 f = 0 で初期化する.* 次数は N 未満とし,溢れた分は切り捨てられる.** BFPS<N>(bool c0, int n = 1) : O(1)* n 次未満の項をもつ定数多項式 f = c0 で初期化する.** BFPS<N>(bitset c, int n) : O(n / 64)* f(x) = c[0] + c[1] z + ... + c[n-1] z^(n-1) で初期化する.** c + f, f + c : O(1) f + g : O(n / 64)* f * g : O(n^2 / 64) f * g_sp : O(n |g|)* f / g : O(n^2 / 64) f / g_sp : O(n |g|)* 形式的冪級数としての和,積,商の結果を返す.* g_sp はスパース多項式であり,係数が 1 である次数を昇順に並べた vector で表す.* 制約 : 商では g(0) = 1** BFPS f.inv(int d) : O(n^2 / 64)* 1 / f mod z^d を返す.* 制約 : f(0) = 1** BFPS f.quotient(BFPS g) : O(n^2 / 64)* BFPS f.reminder(BFPS g) : O(n^2 / 64)* pair<BFPS, BFPS> f.quotient_remainder(BFPS g) : O(n^2 / 64)* 多項式としての f を g で割った商,余り,商と余りの組を返す.* 制約 : g の最項次の項の係数は 1** BFPS f.quotient(SFPS g) : O((n + deg(g)) |g|)* BFPS f.reminder(SFPS g) : O((n + deg(g)) |g|)* pair<BFPS, BFPS> f.quotient_remainder(SFPS g) : O((n + deg(g)) |g|)* 多項式としての f を g で割った商,余り,商と余りの組を返す.* 制約 : g の最項次の項の係数は 1** int f.deg(), int f.size() : O(1)* 多項式 f の次数[+1]を返す.** BFPS::monomial(int d) : O(d / 64)* 単項式 z^d を返す.** int popcount() : O(n / 64)* 項数を返す.** f.resize(int d) : O(1)* mod z^d をとる.** f.resize() : O(n / 64)* 不要な高次の項を削る.** f >> d, f << d : O(n / 64)* 係数列を d だけ右[左]シフトした多項式を返す.* (右シフトは z^d の乗算,左シフトは z^d で割った商と等価)*/template <int N>struct BFPS {using SFPS = vi;int n; // 係数の個数(次数 + 1)bitset<N> c; // 係数列// コンストラクタ(零元,定数,係数列で初期化)BFPS() : n(0) {}BFPS(bool c0, int n = 1) : n(n) { c[0] = c0; }BFPS(const bitset<N>& c, int n) : n(n), c(c) {}// 代入BFPS(const BFPS& f) = default;BFPS& operator=(const BFPS& f) = default;BFPS& operator=(bool c0) { n = 1; c.reset(); c[0] = c0; return *this; }// 比較bool operator==(const BFPS& g) const { return c == g.c; }bool operator!=(const BFPS& g) const { return c != g.c; }// アクセスbool operator[](int i) const { return c[i]; }typename bitset<N>::reference operator[](int i) { return c[i]; }// 次数int deg() const { return n - 1; }int size() const { return n; }// 加算BFPS& operator+=(const BFPS& g) {chmax(n, g.n); c ^= g.c;return *this;}BFPS operator+(const BFPS& g) const { return BFPS(*this) += g; }// 定数加算BFPS& operator+=(bool sc) {chmax(n, 1); c[0] = c[0] ^ sc;return *this;}BFPS operator+(bool sc) const { return BFPS(*this) += sc; }friend BFPS operator+(bool sc, const BFPS& f) { return f + sc; }// 積BFPS& operator*=(const BFPS& g) {// verify : https://atcoder.jp/contests/abc009/tasks/abc009_4n += g.n - 1;bitset<N> res;rep(i, g.n) if (g[i]) res ^= c << i;c = move(res);return *this;}BFPS operator*(const BFPS& g) const { return BFPS(*this) *= g; }// 除算BFPS inv(int d) const {Assert(n >= 1 && c[0]);BFPS res(1, d);bitset<N> mul(c);repi(i, 1, d - 1) {if (mul[i]) {res[i] = 1;mul ^= c << i;}}bitset<N> mask; mask.set(); mask >>= N - d;res.c &= mask;return res;}BFPS& operator/=(const BFPS& g) { return *this *= g.inv(n); }BFPS operator/(const BFPS& g) const { return BFPS(*this) /= g; }// 余り付き除算pair<BFPS, BFPS> quotient_remainder(const BFPS& g) const {BFPS q, r(c, g.n - 1);repir(i, n - 1, g.n - 1) {if (r[i]) {q[i - g.n + 1] = 1;r.c ^= g.c << (i - g.n + 1);}}q.n = n - r.n;return make_pair(q, r);}BFPS quotient(const BFPS& g) const {// verify : https://atcoder.jp/contests/arc084/tasks/arc084_dreturn quotient_remainder(g).first;}BFPS reminder(const BFPS& g) const { return quotient_remainder(g).second; }// スパース積BFPS& operator*=(const SFPS& g) {n += *g.rbegin();bitset<N> res;repe(i, g) res ^= c << i;c = res;return *this;}BFPS operator*(const SFPS& g) const { return BFPS(*this) *= g; }// スパース商BFPS& operator/=(const SFPS& g) {// g の定数項だけ例外処理auto it0 = g.begin();Assert(*it0 == 0);it0++;// 前からインライン配る DP(後ろに累積効果あり)rep(i, n) {// 上位項に係数倍して配っていく.for (auto it = it0; it != g.end(); it++) {if (i + *it >= n) break;c[i + *it] = c[i + *it] ^ c[i];}}return *this;}BFPS operator/(const SFPS& g) const { return BFPS(*this) /= g; }// スパース余り付き除算pair<BFPS, BFPS> quotient_remainder(const SFPS& g) const {// verify : https://atcoder.jp/contests/arc147/tasks/arc147_fBFPS q, r(c, g.back());repir(i, n - 1, g.back()) {if (r[i]) {q[i - g.back()] = 1;repe(j, g) r[i + j - g.back()] = r[i + j - g.back()] ^ 1;}}q.n = n - r.n;return make_pair(q, r);}BFPS quotient(const SFPS& g) const { return quotient_remainder(g).first; }BFPS reminder(const SFPS& g) const { return quotient_remainder(g).second; }// 単項式 z^d を返す.static BFPS monomial(int d) {BFPS mono(0, d + 1);mono[d] = 1;return mono;}// 1 になっているビットの数を返す.int popcount() const {// verify : https://atcoder.jp/contests/arc156/tasks/arc156_dreturn (int)c.count();}// 不要な高次項の除去(最高次の係数が非 0 になるまで削る)BFPS& resize() {while (n > 0 && !c[n - 1]) n--;return *this;}// 高次項の除去(z^d 以上の項を除去する)BFPS& resize(int d) {n = d;bitset<N> mask; mask.set(); mask >>= N - d;c &= mask;return *this;}// 係数のシフトBFPS& operator>>=(int d) { n += d; c <<= d; return *this; }BFPS& operator<<=(int d) { n = max(n - d, 0); c >>= d; return *this; }BFPS operator>>(int d) const { return BFPS(*this) >>= d; }BFPS operator<<(int d) const { return BFPS(*this) <<= d; }#ifdef _MSC_VERfriend ostream& operator<<(ostream& os, const BFPS& f) {if (f.n == 0) os << 0;else {rep(i, f.n) {os << f[i] << "z^" << i;if (i < f.n - 1) os << " + ";}}return os;}#endif};//【累乗の項数】O(2^(deg g) (deg g)^2 log m / 64)/** f(z) g(z)^m の項数を返す.** 制約:deg f ≦ deg g, 2 deg g < N*/template <int N>ll count_pow_terms(BFPS<N> f, const BFPS<N>& g, ll m) {// verify : https://projecteuler.net/problem=588//【方法】// m の第 i ビットを m[i] と書くことにすると,f(z) g(z)^m は// f(z) g(z)^m = f(z) Πi≧0 (g(z)^(2^i))^m[i]// と表される.さらに F_2[z] においては 2 乗(フロベニウス写像)は環準同型なので// f(z) g(z)^m = f(z) Πi≧0 g(z^(2^i))^m[i]// となる.//// まず第 0 ビットについて考える.i=0 の部分の積を偶関数部分と奇関数部分に分けて// f(z) g(z)^m[0] = F_e(z^2) + z F_o(z^2)// とおくと,i≧1 のときの z^(2^i) が偶関数であることから,偶数次の項は// F_e(z^2) Πi≧1 g(z^(2^i))^m[i]// 奇数次の項は// z F_o(z^2) Πi≧1 g(z^(2^i))^m[i]// で全てであり,それぞれの項数は// F_e(z) Πi≧0 g(z^(2^i))^(m/2)[i]// F_o(z) Πi≧0 g(z^(2^i))^(m/2)[i]// と変わらない.// deg F_e(z), deg F_o(z) ≦ deg g// なので,次数が deg g 以下の bit 多項式全てを状態にもって bitDP すればよい.int n = sz(g);f.resize(n);vector<BFPS<N>> fs(1LL << n);repb(set, n) fs[set] = BFPS<N>(bitset<N>(set), n);vl dp(1LL << n);dp[f.c.to_ulong()] = 1;while (m > 0) {vl ndp(1LL << n);repb(set, n) {BFPS<N> f(fs[set]);if (m % 2 == 1) f *= g;f.resize(2 * n);int nset0 = 0;rep(i, n) nset0 |= (int)f[2 * i] << i;ndp[nset0] += dp[set];int nset1 = 0;rep(i, n) nset1 |= (int)f[2 * i + 1] << i;ndp[nset1] += dp[set];}dp = move(ndp);m /= 2;}ll res = 0;repb(set, n) res += dp[set] * popcount(set);return res;}//【局面の勝敗】O(?)(遅いので実験用)/** 先手番での初期局面 p_ini から遷移可能な局面とその勝敗を {{手番, 局面}, 勝敗} で表したリストを返す.* nxt(t, p, nps) を呼ぶと,t=1:先手番[t=0:後手番] での局面 p から遷移可能な局面のリストを nps に格納する.* ただし nps が空の場合は,先手勝ちなら 1,後手勝ちなら 0 を返すようにする.*/using T = tuple<int, int, int, int, int>;map<pair<int, T>, int> res;void decide_WL(const T& p_ini, function<int(int, const T&, vector<T>&)>& nxt) {// verify : https://atcoder.jp/contests/abc349/tasks/abc349_e// t=1:先手番[t=0:後手番] で局面 p であるときの勝敗を返す.function<int(int, const T&)> dfs = [&](int t, const T& p) {// 既に勝敗が確定済ならその結果を返す.if (res.count({ t, p })) return res[{t, p}];// 局面 p から遷移可能な局面の集合 nps を得る.vector<T> nps;int wl = nxt(t, p, nps);// p から遷移可能な局面が無い場合は決着.if (nps.empty()) {res[{t, p}] = wl;return wl;}// 遷移先に自分勝ちの局面が全く無ければ相手勝ちres[{t, p}] = 1 - t;// 遷移先に自分勝ちの局面が 1 つでもあれば自分勝ちrepe(np, nps) {if (dfs(1 - t, np) == t) {res[{t, p}] = t;}}return res[{t, p}];};dfs(1, p_ini);/* nxt の定義の雛形using T = tuple<ll, ll, vl>;function<int(int, const T&, vector<T>&)> nxt = [&](int t, const T& p, vector<T>& nps) {ll l, r; vl a;tie(l, r, a) = p;return 0;};*/}void zikken_even() {function<int(int, const T&, vector<T>&)> nxt = [&](int t, const T& p, vector<T>& nps) {auto [c0, c1, d0, d1, sc] = p;if (c0 + c1 == 0) {if (sc % 2 == 0) return 1;else return 0;}if (c0 > 0 && d0 > 0) {nps.push_back({ c0 - 1, c1, d0 - 1 , d1, sc });}if (c0 > 0 && d1 > 0) {nps.push_back({ c0 - 1, c1, d0 , d1 - 1, sc });}if (c1 > 0 && d0 > 0) {nps.push_back({ c0, c1 - 1, d0 - 1 , d1, sc });}if (c1 > 0 && d1 > 0) {nps.push_back({ c0, c1 - 1, d0 , d1 - 1, sc + 1 });}return 0;};repi(n, 1, 10) repi(c0, 0, n) {int c1 = n - c0;int d0 = n / 2;int d1 = n - d0;T ini = T{ c0, c1, d0, d1, 0 };decide_WL(ini, nxt);int g = res[{1, ini}];// if (g == 0) {dump("c:", c0, c1, " d:", d0, d1, " :", g);// }}exit(0);}void zikken() {int n = 20;vvvi dp(n + 1, vvi(n + 1, vi(n + 1)));dp[0][0][0] = 0b01;repi(c0, 0, n) repi(c1, 0, n) repi(d0, 0, n) {if (c0 + c1 == 0) continue;int d1 = c0 + c1 - d0;if (d1 < 0 || d1 > n) continue;int x = 0;if (c0 > 0 && d0 > 0) {// even にしたいとき even にできるか?// → 相手に手を渡したあと,相手が odd にしたいと思っていても odd にできない局面が 1 つでもあるか?x |= getb(~dp[c0 - 1][c1][d0 - 1], 1) << 0;x |= getb(~dp[c0 - 1][c1][d0 - 1], 0) << 1;}if (c0 > 0 && d1 > 0) {x |= getb(~dp[c0 - 1][c1][d0], 1) << 0;x |= getb(~dp[c0 - 1][c1][d0], 0) << 1;}if (c1 > 0 && d0 > 0) {x |= getb(~dp[c0][c1 - 1][d0], 1) << 0;x |= getb(~dp[c0][c1 - 1][d0], 0) << 1;}if (c1 > 0 && d1 > 0) {x |= getb(~dp[c0][c1 - 1][d0], 0) << 0;x |= getb(~dp[c0][c1 - 1][d0], 1) << 1;}dp[c0][c1][d0] = x;}// dumpel(dp);repi(c0, 0, n) {repi(c1, 0, n) {int s = c0 + c1;int d0 = s / 2;int d1 = s - d0;int g = dp[c0][c1][d0];if (g != 0) cout << g << " ";else cout << "." << " ";}cout << endl;}//repi(s, 1, n) repi(c0, 0, s) {// int c1 = s - c0;// int d0 = s / 2;// int d1 = s - d0;// int g = dp[c0][c1][d0];// dump("c:", c0, c1, " d:", d0, d1, " :", bitset<2>(g));//}exit(0);}/*1 2 . 3 3 . . 3 3 . . 3 3 . . 3 3 . . 3 31 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 31 3 . 3 . 3 3 . . 3 3 . . 3 3 . . 3 3 . .1 3 3 . 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 31 3 . 3 . 3 . 3 3 . . 3 3 . . 3 3 . . 3 31 3 3 . 3 . 3 3 3 3 3 3 3 3 3 3 3 3 3 3 31 3 . 3 . 3 . 3 . 3 3 . . 3 3 . . 3 3 . .1 3 3 . 3 . 3 . 3 3 3 3 3 3 3 3 3 3 3 3 31 3 . 3 . 3 . 3 . 3 . 3 3 . . 3 3 . . 3 31 3 3 . 3 . 3 . 3 . 3 3 3 3 3 3 3 3 3 3 31 3 . 3 . 3 . 3 . 3 . 3 . 3 3 . . 3 3 . .1 3 3 . 3 . 3 . 3 . 3 . 3 3 3 3 3 3 3 3 31 3 . 3 . 3 . 3 . 3 . 3 . 3 . 3 3 . . 3 31 3 3 . 3 . 3 . 3 . 3 . 3 . 3 3 3 3 3 3 31 3 . 3 . 3 . 3 . 3 . 3 . 3 . 3 . 3 3 . .1 3 3 . 3 . 3 . 3 . 3 . 3 . 3 . 3 3 3 3 31 3 . 3 . 3 . 3 . 3 . 3 . 3 . 3 . 3 . 3 31 3 3 . 3 . 3 . 3 . 3 . 3 . 3 . 3 . 3 3 31 3 . 3 . 3 . 3 . 3 . 3 . 3 . 3 . 3 . 3 .1 3 3 . 3 . 3 . 3 . 3 . 3 . 3 . 3 . 3 . 31 3 . 3 . 3 . 3 . 3 . 3 . 3 . 3 . 3 . 3 .*/int solve(ll c0, ll c1) {ll n = c0 + c1;ll d0 = n / 2;ll d1 = n - d0;// dump(d0, d1);int res = -1;if (c1 == 0) {res = 1;}else if (c1 == 1) {if (c0 == 0) {res = 2;}else {res = 3;}}else if (c0 >= c1 - 1) {if ((c0 + c1) % 2 == 0) {res = 0;}else {res = 3;}}else if (c0 % 2 == 1) {res = 3;}else if (c0 % 4 == 0) {if (c1 % 4 == 1 || c1 % 4 == 2) {res = 0;}else {res = 3;}}else {if (c1 % 4 == 1 || c1 % 4 == 2) {res = 3;}else {res = 0;}}return res;}void check() {int n = 20;repi(c0, 0, n) {repi(c1, 0, n) {int g = solve(c0, c1);if (g != 0) cout << g << " ";else cout << "." << " ";}cout << endl;}exit(0);}/*1 2 . 3 3 . . 3 3 . . 3 3 . . 3 3 . . 3 31 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 31 3 . 3 . 3 3 . . 3 3 . . 3 3 . . 3 3 . .1 3 3 . 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 31 3 . 3 . 3 . 3 3 . . 3 3 . . 3 3 . . 3 31 3 3 . 3 . 3 3 3 3 3 3 3 3 3 3 3 3 3 3 31 3 . 3 . 3 . 3 . 3 3 . . 3 3 . . 3 3 . .1 3 3 . 3 . 3 . 3 3 3 3 3 3 3 3 3 3 3 3 31 3 . 3 . 3 . 3 . 3 . 3 3 . . 3 3 . . 3 31 3 3 . 3 . 3 . 3 . 3 3 3 3 3 3 3 3 3 3 31 3 . 3 . 3 . 3 . 3 . 3 . 3 3 . . 3 3 . .1 3 3 . 3 . 3 . 3 . 3 . 3 3 3 3 3 3 3 3 31 3 . 3 . 3 . 3 . 3 . 3 . 3 . 3 3 . . 3 31 3 3 . 3 . 3 . 3 . 3 . 3 . 3 3 3 3 3 3 31 3 . 3 . 3 . 3 . 3 . 3 . 3 . 3 . 3 3 . .1 3 3 . 3 . 3 . 3 . 3 . 3 . 3 . 3 3 3 3 31 3 . 3 . 3 . 3 . 3 . 3 . 3 . 3 . 3 . 3 31 3 3 . 3 . 3 . 3 . 3 . 3 . 3 . 3 . 3 3 31 3 . 3 . 3 . 3 . 3 . 3 . 3 . 3 . 3 . 3 .1 3 3 . 3 . 3 . 3 . 3 . 3 . 3 . 3 . 3 . 31 3 . 3 . 3 . 3 . 3 . 3 . 3 . 3 . 3 . 3 .*/int main() {// input_from_file("input.txt");// output_to_file("output.txt");// zikken_even();// zikken();// check();int t;cin >> t;constexpr int N = 4;BFPS<N> f(1);BFPS<N> g(bitset<4>(3), 2);dump(f); dump(g);rep(hoge, t) {ll n; string s;cin >> n >> s;ll c1 = count_pow_terms<4>(f, g, n - 1);ll c0 = n - c1;dump(c0, c1);int res = solve(c0, c1);if (s == "Even") {cout << ((res & 1) ? "Alice" : "Bob") << endl;}else {cout << ((res & 2) ? "Alice" : "Bob") << endl;}}}