接龙

题目描述

高桥词典中收录了 $N$ 个单词，第 $i$ 个单词（ $1 \le i \le N$ ）为 $s_i$ 。

使用这本词典，高桥和青木将玩「3-shiritori」游戏，规则如下。

高桥和青木轮流说单词，高桥先手。
每个玩家必须说一个以「前一个单词的最后三个字符」开头的单词。例如，如果某个玩家说了 Takahashi，下一个玩家可以说 ship 或 shield（以及其他选择），但不能说 Aoki、sing 或 his。
区分大小写。例如，不能在 Takahashi 之后说 ShIp。
无法说出单词的玩家输。
不能说出词典中没有收录的单词。
同一个单词可以多次使用。

对于每个 $i$ （ $1 \le i \le N$ ），判断当高桥以说出单词 $s_i$ 开始游戏时谁会获胜。这里，假设双方都采取最优策略。更具体地说，每位玩家把「避免自己输」作为第一优先，把「击败对手」作为第二优先。

输入按以下格式从标准输入给出：

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

输出 $N$ 行。第 $i$ 行（ $1 \le i \le N$ ）：当高桥以说出单词 $s_i$ 开始游戏时，如果高桥获胜，输出 Takahashi；如果青木获胜，输出 Aoki；如果游戏无限持续且无人输，输出 Draw。

3
abcd
bcda
ada

Aoki
Takahashi
Draw

当高桥以说出 abcd 开始时，青木接着会说 bcda，随后高桥没有可说的单词，青木获胜。因此应输出 Aoki。

当高桥以说出 bcda 开始时，青木没有可说的单词，高桥获胜。因此应输出 Takahashi。

当高桥以说出 ada 开始时，双方会不断重复 ada，游戏永不结束。因此应输出 Draw。注意同一个单词可以无限次使用。

1
ABC

Draw

5
eaaaabaa
eaaaacaa
daaaaaaa
eaaaadaa
daaaafaa

Takahashi
Takahashi
Takahashi
Aoki
Takahashi

难度提高

通过率 —

尝试 0

已通过 0

标签