# generated by AI import sys from typing import List # <-- 変更点(1):List をインポート def solve(s: str) -> int: """ 事前計算された遷移行列を用いて、文字列sに対するNim値を計算する。 """ # --------------- C++コードから移植された定数 ---------------- DIM = 3 COL = 2 # matAs[col][i][j] は、状態iから状態jへの遷移(文字col)を表す # C++コードの matAs[COL][DIM][DIM] に対応 matAs = [ # c = '0' (A) [ [0, 1, 0], [1, 0, 0], [-2, 2, 1] ], # c = '1' (B) [ [0, 0, 1], [-2, 1, 2], [1, 0, 0] ] ] # C++コードの vecP[DIM] に対応 vecP = [0, 0, 1] # -------------------------------------------------------------- # dpベクトル(状態ベクトル)の初期化 dp = [0] * DIM dp[0] = 1 # C++の apply 関数に相当する行列ベクトル積 # 変更点(2): list[int] -> List[int] に変更 def apply_matrix(x: List[int], col: int) -> List[int]: """ 現在の状態ベクトル x に、文字 col に対応する遷移行列を掛ける。 z = x * M (xは行ベクトル) z[j] = sum(x[i] * M[i][j] for i) """ z = [0] * DIM M = matAs[col] for j in range(DIM): for i in range(DIM): z[j] += x[i] * M[i][j] return z # 文字列sを左から読み込み、状態を更新していく for char_code in s: col = int(char_code) # '0' または '1' dp = apply_matrix(dp, col) # 最終的な状態ベクトル dp と 終端ベクトル vecP の内積を計算 res = 0 for i in range(DIM): res += dp[i] * vecP[i] return res def main(): """ メインの実行部分 """ # sys.stdin.readline を使うと高速 try: n_str = sys.stdin.readline() if not n_str: return # 入力が空の場合 n = int(n_str.strip()) s = sys.stdin.readline().strip() if len(s) != n: # 必要に応じてエラーハンドリング pass # 'A'を'0'に、'B'を'1'に変換 s_numeric = s.replace('A', '0').replace('B', '1') # solve関数を呼び出してNim値(Grundy数)を計算 nim_value = solve(s_numeric) # Nim値が0なら後手必勝(Bob)、0以外なら先手必勝(Alice) if nim_value != 0: print("Alice") else: print("Bob") except EOFError: pass except Exception as e: print(f"An error occurred: {e}", file=sys.stderr) if __name__ == "__main__": main()