AT_abc278_f [ABC278F] Shiritori

题目描述

给定 $N$ 个字符串 $S_1, S_2, \ldots, S_N$。每个 $S_i\ (1\leq i\leq N)$ 都是由小写英文字母组成的非空字符串，长度不超过 $10$，且互不相同。

太郎君（先手）和次郎君（后手）进行“接龙”游戏。两人轮流操作，太郎君先手。每一回合，当前玩家需要选择一个整数 $i\ (1\leq i\leq N)$，并满足以下两个条件：

• $i$ 不能等于之前所有回合中已经被选择过的任意整数；
• 如果这不是第一回合，设上一次选择的整数为 $j$，则 $S_j$ 的最后一个字母必须等于 $S_i$ 的第一个字母。

如果某位玩家无法选择满足条件的 $i$，则该玩家输，另一位玩家获胜。

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

输入格式

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

$N$
$S_1$
$S_2$
$\vdots$
$S_N$

输出格式

如果先手太郎君获胜，输出 First；如果后手次郎君获胜，输出 Second。

输入输出样例 #1

输入 #1

6
enum
float
if
modint
takahashi
template

输出 #1

First

输入输出样例 #2

输入 #2

10
catch
chokudai
class
continue
copy
exec
havoc
intrinsic
static
yucatec

输出 #2

Second

输入输出样例 #3

输入 #3

16
mnofcmzsdx
lgeowlxuqm
ouimgdjxlo
jhwttcycwl
jbcuioqbsj
mdjfikdwix
jhvdpuxfil
peekycgxco
sbvxszools
xuuqebcrzp
jsciwvdqzl
obblxzjhco
ptobhnpfpo
muizaqtpgx
jtgjnbtzcl
sivwidaszs

输出 #3

First

说明/提示

限制条件

• $1 \leq N \leq 16$
• $N$ 为整数
• $S_i\ (1\leq i\leq N)$ 是由小写英文字母组成的非空字符串，长度不超过 $10$
• $S_i \neq S_j\ (1\leq i < j \leq N)$

样例解释 1

例如，游戏可以如下进行。注意，这个过程中的两人操作不一定都是最优的。

• 先手太郎君选择 $i=3$，$S_i=$if。
• 后手次郎君选择 $i=2$，$S_i=$float，且 if 的最后一个字母和 float 的第一个字母相同。
• 先手太郎君选择 $i=5$，$S_i=$takahashi，且 float 的最后一个字母和 takahashi 的第一个字母相同。
• 后手次郎君无法选择 $i\neq2,3,5$ 且 $S_i$ 的第一个字母为 i 的字符串，因此失败。

此时，先手太郎君获胜。

由 ChatGPT 4.1 翻译