Shiritori

题目描述

给定 $N$ 个字符串 $S _ 1,S _ 2,\ldots,S _ N$。 $S _ i\ (1\leq i\leq N)$ 是长度至多为 $10$ 的非空小写英文字母字符串，且这些字符串两两不同。 太郎（Taro the First）和次郎（Jiro the Second）进行一个接龙游戏。 在该游戏中，两名玩家交替进行回合， 太郎先手。 在每个玩家的回合中，玩家选择一个整数 $i\ (1\leq i\leq N)$， 该整数应当满足以下两个条件：

$i$ 与自游戏开始以来两名玩家已经选择过的任何整数都不同； 当前回合要么是游戏的第一个回合，要么若上一个被选择的整数为 $j$，则 $S_j$ 的最后一个字符与 $S_i$ 的第一个字符相等。

无法选择符合条件的 $i$ 的玩家输；另一个玩家获胜。 假设双方都采取最优策略，判断哪位玩家会获胜。

输入格式

输入从标准输入按以下格式给出： $N$ $S_1$ $S_2$ $\vdots$ $S_N$

输出格式

若双方都采取最优策略，若太郎先手获胜则输出 $First$；若次郎后手获胜则输出 $Second$。

6
enum
float
if
modint
takahashi
template

First

10
catch
chokudai
class
continue
copy
exec
havoc
intrinsic
static
yucatec

Second

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

First

提示

$1 \leq N \leq 16$ $N$ 是整数。 $S _ i\ (1\leq i\leq N)$ 是长度至多为 $10$ 的非空小写英文字母字符串。 $S _ i\neq S _ j\ (1\leq i\lt j\leq N)$例如，游戏进程如下所示。 注意在此示例中两名玩家可能并未采取最优策略。

太郎先手选择 $i=3$。 $S _ i=$$if$。 次郎选择 $i=2$。 $S _ i=$$float$，且 $if$ 的最后一个字符等于 $float$ 的第一个字符。 太郎选择 $i=5$。 $S _ i=$$takahashi$，且 $float$ 的最后一个字符等于 $takahashi$ 的第一个字符。 次郎无法选择不等于 $2,3,5$ 的 $i$ 使得 $S _ i$ 以 $i$ 开头（注：原文意为以相应字符开头），因此他输。

在这种情况下，太郎先手获胜。

标签: AtCoder|abc278F

来源

AtCoder|abc278F