Lucky 7 Battle

题目描述

我们有一个长度为 $N$ 的字符串 $S$，由 $0$，$\ldots$，$9$ 组成，和一个长度为 $N$ 的字符串 $X$，由 $A$ 和 $T$ 组成。此外，还有一个字符串 $T$，初始化为空字符串。 Takahashi 和 Aoki 将使用这些来进行一个游戏。游戏由 $N$ 轮组成。在第 $i$ 轮 $(1\leq i \leq N)$，发生以下情况：

如果 $X_i$ 是 $A$，Aoki 执行下面的操作；如果 $X_i$ 是 $T$，Takahashi 执行它。 操作：在 $T$ 的末尾追加 $S_i$ 或 $0$。

在 $N$ 次操作之后，$T$ 将成为一个长度为 $N$ 的由 $0$，$\ldots$，$9$ 组成的字符串。 如果去掉前导零后 $T$ 作为十进制数是 $7$ 的倍数，Takahashi 获胜；否则，Aoki 获胜。 当两名玩家都以最优策略进行时，确定游戏的胜者。

输入格式

输入从标准输入按以下格式给出： $N$ $S$ $X$

输出格式

如果在两名玩家都以最优策略进行时 Takahashi 获胜，输出 $Takahashi$；如果 Aoki 获胜，输出 $Aoki$。

2
35
AT

Takahashi

5
12345
AAAAT

Aoki

5
67890
TTTTA

Takahashi

5
12345
ATATA

Aoki

提示

$1 \leq N \leq 2\times 10^5$ $S$ 和 $X$ 的长度均为 $N$。 $S$ 由 $0$，$\ldots$，$9$ 组成。 $X$ 由 $A$ 和 $T$ 组成。在第 1 轮，Aoki 在 $T$ 的末尾追加 $3$ 或 $0$。在第 2 轮，Takahashi 在末尾追加 $5$ 或 $0$。 如果 Aoki 追加 $3$，Takahashi 可以追加 $5$ 使 $T$ 成为 $35$，这是 $7$ 的倍数。 如果 Aoki 追加 $0$，Takahashi 可以追加 $0$ 使 $T$ 成为 $00$，这是 $7$ 的倍数。 因此，Takahashi 总能获胜。

标签: AtCoder|abc195E

来源

AtCoder|abc195E