← 返回题目列表

AtCoder · agc063_a

A. 墨西哥游戏

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

给你一个长度为 N+1 组成 A 和 B: S = S_0\cdots S_N。 对于每个 k=1, \ldots, N,解决以下问题。

Alice 和 Bob 将使用一组玩游戏 X,最初是空的。对于 t=1,\ldots, k 按照此顺序,他们将执行以下操作:

  • if t 是奇数,Alice 会选择一个非负整数 x 并替换 X 与 X\cup \{x\};
  • if t 是偶数,Bob 会选择一个非负整数 x 并替换 X 与 X\cup \{x\}.

让 x be \mathrm{mex}(X) 毕竟 k 行动。如果角色 S_x is A,爱丽丝获胜;如果 S_x is B,鲍勃获胜。请注意 X 最多有 k 元素,所以 x = \mathrm{mex}(X) \leq k 和角色 S_x 存在。

当两名玩家都发挥最佳状态时打印获胜者的姓名。

什么是 \mathrm{mex}(X)? 对于有限集 X 由非负整数组成, \mathrm{mex}(X) 是最小的非负整数 x 这样 x\notin X.

约束

  • 1\leq N\leq 2\times 10^5
  • S 是一个长度为 N+1 组成 A 和 B.

输入

输入由标准输入按以下格式给出:

N
S

输出

打印 N 行。的 i- 第行应包含获胜者的姓名 (Alice or Bob)当双方都在游戏中发挥最佳水平时 k=i.


示例输入 1

2
ABB

示例输出 1

Alice
Bob

这是游戏的可能进展 k=1.

  • 爱丽丝选择 x=10.
  • \mathrm{mex}(X)=\mathrm{mex}(\lbrace 10\rbrace) = 0,和 S_0 is A,所以爱丽丝获胜。

这是游戏的可能进展 k=2.

  • 爱丽丝选择 x=2.
  • 鲍勃选择 x=0.
  • \mathrm{mex}(X)=\mathrm{mex}(\lbrace 0,2\rbrace) = 1,和 S_1 is B,所以鲍勃获胜。

示例输入 2

4
AAAAA

示例输出 2

Alice
Alice
Alice
Alice

示例输入 3

7
BBAABABA

示例输出 3

Bob
Bob
Alice
Bob
Alice
Bob
Alice