AT_abc209_e [ABC209E] Shiritori

题目描述

高桥词典中收录了 $N$ 个单词，第 $i$ 个单词为 $s_i$。

高桥君和青木君将使用高桥词典进行“三字接龙”游戏。三字接龙的规则如下：

• 两人轮流说单词，从高桥君开始。
• 每位玩家必须说出一个以前一位玩家所说单词最后 $3$ 个字母开头的单词。例如，前一位说了 Takahashi，则下一位可以说 ship、shield 等，但不能说 Aoki、sing、his 等。
• 大小写字母视为不同。例如，Takahashi 后不能说 ShIp。
• 如果无法说出单词，则判负。
• 只能说词典中收录的单词。
• 同一个单词可以重复使用任意次数。

对于每个 $i\ (1 \leq i \leq N)$，请判断如果高桥君以单词 $s_i$ 开始三字接龙，最终谁会获胜。假设两人都采取最优策略，即优先保证自己不输，其次优先让对方输。

输入格式

输入按以下格式从标准输入读入：

$N$
$s_1$
$s_2$
$\vdots$
$s_N$

输出格式

输出 $N$ 行。第 $i$ 行输出：如果高桥君以单词 $s_i$ 开始三字接龙，高桥君获胜则输出 Takahashi，青木君获胜则输出 Aoki，若接龙永远无法结束则输出 Draw。

输入输出样例 #1

输入 #1

3
abcd
bcda
ada

输出 #1

Aoki
Takahashi
Draw

输入输出样例 #2

输入 #2

1
ABC

输出 #2

Draw

输入输出样例 #3

输入 #3

5
eaaaabaa
eaaaacaa
daaaaaaa
eaaaadaa
daaaafaa

输出 #3

Takahashi
Takahashi
Takahashi
Aoki
Takahashi

说明/提示

数据范围

• $N$ 是 $1$ 到 $2 \times 10^5$ 之间的整数。
• $s_i$ 由英文字母（大小写区分）组成，长度在 $3$ 到 $8$ 之间。

样例解释 1

当高桥君以 abcd 开始时，青木君可以接 bcda，此时高桥君无法继续接龙，因此青木君获胜，应输出 Aoki。
当高桥君以 bcda 开始时，青木君无法继续接龙，因此高桥君获胜，应输出 Takahashi。
当高桥君以 ada 开始时，双方可以一直重复说 ada，接龙永远不会结束，因此应输出 Draw。注意，同一个单词可以重复使用任意次数。

由 ChatGPT 4.1 翻译