AT_abc195_e [ABC195E] Lucky 7 Battle

题目描述

给定一个由 0 到 9 组成的长度为 $N$ 的字符串 $S$，以及一个由 A、T 组成的长度为 $N$ 的字符串 $X$。此外，还有一个初始为空字符串的字符串 $T$。

高桥君和青木君将用这些字符串进行游戏。游戏共进行 $N$ 轮，在第 $i$ 轮（$1 \leq i \leq N$）中，进行如下操作：

• 如果 $X_i$ 是 A，则青木君操作；如果 $X_i$ 是 T，则高桥君操作。
• 操作内容：在 $T$ 的末尾添加 $S_i$ 或 0 中的任意一个字符。

经过 $N$ 次操作后，$T$ 变为一个由 0 到 9 组成的长度为 $N$ 的字符串。将 $T$ 去除前导多余的 $0$ 后，视为一个十进制数。如果这个数是 $7$ 的倍数，则高桥君获胜，否则青木君获胜。

请判断当两人都采取最优策略时，谁会获胜。

输入格式

输入以以下格式从标准输入读入。

$N$ $S$ $X$

输出格式

如果高桥君获胜，输出 Takahashi；如果青木君获胜，输出 Aoki。

输入输出样例 #1

输入 #1

2
35
AT

输出 #1

Takahashi

输入输出样例 #2

输入 #2

5
12345
AAAAT

输出 #2

Aoki

输入输出样例 #3

输入 #3

5
67890
TTTTA

输出 #3

Takahashi

输入输出样例 #4

输入 #4

5
12345
ATATA

输出 #4

Aoki

说明/提示

限制条件

• $1 \leq N \leq 2 \times 10^5$
• $S, X$ 的长度均为 $N$
• $S$ 仅由 0 到 9 组成
• $X$ 仅由 A 和 T 组成

样例解释 1

第 $1$ 轮青木君可以选择将 3 或 0 添加到 $T$ 的末尾，第 $2$ 轮高桥君可以选择将 5 或 0 添加到 $T$ 的末尾。若青木君添加 3，高桥君添加 5，则 $T$ 变为 35，它是 $7$ 的倍数。若青木君添加 0，高桥君添加 0，则 $T$ 变为 00，它也是 $7$ 的倍数。因此，无论如何，高桥君都能获胜。

由 ChatGPT 4.1 翻译