102094: [AtCoder]ABC209 E - Shiritori
Description
Score : $500$ points
Problem Statement
The Takahashi Dictionary lists $N$ words; the $i$-th word $(1 \leq i \leq N)$ is $s_i$.
Using this dictionary, Takahashi and Aoki will play $3$-shiritori, which goes as follows.
- Takahashi and Aoki alternately say words, with Takahashi going first.
- Each player must say a word beginning with the last three characters of the previous word. For example, if a player says
Takahashi, the next player can sayshiporshieldalong with other choices, but notAoki,sing, orhis. - Uppercase and lowercase are distinguished. For example, a player cannot say
ShIpfollowingTakahashi. - A player who becomes unable to say a word loses.
- A player cannot say a word not listed in the dictionary.
- The same word can be used multiple times.
For each $i$ $(1 \leq i \leq N)$, determine who will win when Takahashi starts the game by saying the word $s_i$. Here, we assume that both players play optimally. More specifically, each player gives first priority to avoiding his loss and second priority to defeating the opponent.
Constraints
- $N$ is an integer between $1$ and $2 \times 10^5$ (inclusive).
- $s_i$ is a string of length between $3$ and $8$ (inclusive) consisting of lowercase and uppercase English letters.
Input
Input is given from Standard Input in the following format:
$N$ $s_1$ $s_2$ $\vdots$ $s_N$
Output
Print $N$ lines. The $i$-th line $(1 \leq i \leq N)$ should contain Takahashi if Takahashi wins when Takahashi starts the game by saying the word $s_i$, Aoki if Aoki wins in that scenario, and Draw if the game continues forever with neither of them losing in that scenario.
Sample Input 1
3 abcd bcda ada
Sample Output 1
Aoki Takahashi Draw
When Takahashi starts the game by saying abcd, Aoki will say bcda next, and Takahashi will then have no word to say, resulting in Aoki's win. Thus, we should print Aoki.
When Takahashi starts the game by saying bcda, Aoki will have no word to say, resulting in Takahashi win. Thus, we should print Takahashi.
When Takahashi starts the game by saying ada, both players will repeat ada and never end the game. Thus, we should print Draw. Note that they can use the same word any number of times.
Sample Input 2
1 ABC
Sample Output 2
Draw
Sample Input 3
5 eaaaabaa eaaaacaa daaaaaaa eaaaadaa daaaafaa
Sample Output 3
Takahashi Takahashi Takahashi Aoki Takahashi
Input
题意翻译
给定 $N$ 个单词，Takahashi 和 Aoki 二人使用这 $N$ 个单词进行成语接龙，二者轮流说出单词，接龙的规则如下： 1. Takahashi 先手， Aoki 后手； 2. 当一个人说出单词后，另一个人必须选择一个单词满足：前一个人说的单词的后三个字母等于此单词的前三个字母，并说出它，如果这个人没有合法的单词可以说出，他输了; 3. 单词可以重复使用，区分大小写。 请你输出先手 Takahashi 从第 $i\ (1\le i\le N)$ 个单词开始说的情况下，且二者都绝顶聪明，游戏的胜负情况。若先手必胜输出 `Takahashi`，后手必胜输出 `Aoki`，平局输出 `Draw`。Output
问题描述
高桥字典中列出了 $N$ 个单词，第 $i$ 个单词 $(1 \leq i \leq N)$ 为 $s_i$。
高桥和青木将使用这个字典玩 3 字头接龙 游戏，规则如下：
- 高桥和青木交替说出单词，由高桥先开始。
- 每个玩家必须说出一个以前一个单词的最后三个字符开头的单词。例如，如果玩家说
Takahashi，下一个玩家可以说ship或shield等，但不能说Aoki，sing或his。 - 区分大小写。例如，玩家不能在
Takahashi之后说ShIp。 - 无法说出单词的玩家输掉游戏。
- 玩家不能说出字典中未列出的单词。
- 同一个单词可以多次使用。
对于每个 $i$ $(1 \leq i \leq N)$，当高桥以单词 $s_i$ 开始游戏时，判断谁会获胜。在这里，我们假设双方都采取最优策略。具体来说，每个玩家首先避免自己的失败，其次优先考虑打败对手。
限制条件
- $N$ 是介于 $1$ 和 $2 \times 10^5$（含）之间的整数。
- $s_i$ 是一个由小写和大写英文字母组成的长度在 $3$ 到 $8$（含）之间的字符串。
输入
从标准输入按以下格式获取输入：
$N$ $s_1$ $s_2$ $\vdots$ $s_N$
输出
打印 $N$ 行。第 $i$ 行 $(1 \leq i \leq N)$ 应包含 Takahashi 如果高桥以单词 $s_i$ 开始游戏并获胜，Aoki 如果在该情况下青木获胜，以及 Draw 如果游戏会无限期地继续下去，双方都不会在该情况下输掉。
样例输入 1
3 abcd bcda ada
样例输出 1
Aoki Takahashi Draw
当高桥以 abcd 开始游戏时，青木接下来会说 bcda，然后高桥将无话可说，结果青木获胜。因此，我们应该打印 Aoki。
当高桥以 bcda 开始游戏时，青木将无话可说，结果高桥获胜。因此，我们应该打印 Takahashi。
当高桥以 ada 开始游戏时，双方会重复说 ada，游戏永远不会结束。因此，我们应该打印 Draw。注意，他们可以任意次数地使用同一个单词。
样例输入 2
1 ABC
样例输出 2
Draw
样例输入 3
5 eaaaabaa eaaaacaa daaaaaaa eaaaadaa daaaafaa
样例输出 3
Takahashi Takahashi Takahashi Aoki Takahashi