102785: [AtCoder]ABC278 F - Shiritori
Description
Score : $500$ points
Problem Statement
You are given $N$ strings $S _ 1,S _ 2,\ldots,S _ N$. $S _ i\ (1\leq i\leq N)$ is a non-empty string of length at most $10$ consisting of lowercase English letters, and the strings are pairwise distinct.
Taro the First and Jiro the Second play a word-chain game. In this game, the two players take alternating turns, with Taro the First going first. In each player's turn, the player chooses an integer $i\ (1\leq i\leq N)$, which should satisfy the following two conditions:
- $i$ is different from any integer chosen by the two players so far since the game started;
- the current turn is the first turn of the game, or the last character of $S_j$ equals the first character of $S_i$, where $j$ is the last integer chosen.
The player who is unable to choose a conforming $i$ loses; the other player wins.
Determine which player will win if the two players play optimally.
Constraints
- $1 \leq N \leq 16$
- $N$ is an integer.
- $S _ i\ (1\leq i\leq N)$ is a non-empty string of length at most $10$ consisting of lowercase English letters.
- $S _ i\neq S _ j\ (1\leq i\lt j\leq N)$
Input
The input is given from Standard Input in the following format:
$N$ $S_1$ $S_2$ $\vdots$ $S_N$
Output
Print First
if Taro the First wins when the two players play optimally; print Second
if Jiro the Second wins.
Sample Input 1
6 enum float if modint takahashi template
Sample Output 1
First
For example, the game progresses as follows. Note that the two players may not be playing optimally in this example.
- Taro the First chooses $i=3$. $S _ i=$
if
. - Jiro the Second chooses $i=2$. $S _ i=$
float
, and the last character ofif
equals the first character offloat
. - Taro the First chooses $i=5$. $S _ i=$
takahashi
, and the last character offloat
equals the first character oftakahashi
. - Jiro the Second is unable to choose $i\neq2,3,5$ such that $S _ i$ starts with
i
, so he loses.
In this case, Taro the First wins.
Sample Input 2
10 catch chokudai class continue copy exec havoc intrinsic static yucatec
Sample Output 2
Second
Sample Input 3
16 mnofcmzsdx lgeowlxuqm ouimgdjxlo jhwttcycwl jbcuioqbsj mdjfikdwix jhvdpuxfil peekycgxco sbvxszools xuuqebcrzp jsciwvdqzl obblxzjhco ptobhnpfpo muizaqtpgx jtgjnbtzcl sivwidaszs
Sample Output 3
First
Input
题意翻译
给定 $n$ 个不同的字符串。 两人轮流取出一个还未被取出的字符串,要求除先手第一次外,每次取出的字符串的首字符和上一次取出的字符串的尾字符相同。不能操作者输。 问两人均采取最优方案时,先手是否必胜。Output
问题描述
给你 $N$ 个字符串 $S _ 1,S _ 2,\ldots,S _ N$。
$S _ i\ (1\leq i\leq N)$ 是一个长度不超过 $10$ 的非空字符串,由小写英文字母组成,字符串两两不同。
小太郎和次郎玩单词链游戏。在这个游戏中,两个玩家轮流进行,小太郎先走。在每个玩家的回合中,玩家选择一个整数 $i\ (1\leq i\leq N)$,需要满足以下两个条件:
- $i$ 与自游戏开始以来两个玩家选择的任何整数都不同;
- 当前回合是游戏的第一个回合,或者 $S_j$ 的最后一个字符等于 $S_i$ 的第一个字符,其中 $j$ 是最后一个选择的整数。
无法选择符合要求的 $i$ 的玩家输掉游戏;另一个玩家获胜。
如果两个玩家都发挥最佳水平,确定哪个玩家会获胜。
约束
- $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)$
输入
输入通过标准输入以以下格式给出:
$N$ $S_1$ $S_2$ $\vdots$ $S_N$
输出
如果小太郎在两个玩家发挥最佳水平时获胜,则打印 First
;如果次郎获胜,则打印 Second
。
样例输入 1
6 enum float if modint takahashi template
样例输出 1
First
例如,游戏进行如下所示。 请注意,这两个玩家在此示例中可能没有发挥最佳水平。
- 小太郎选择 $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
开头,所以他输掉了比赛。
在这种情况下,小太郎获胜。
样例输入 2
10 catch chokudai class continue copy exec havoc intrinsic static yucatec
样例输出 2
Second
样例输入 3
16 mnofcmzsdx lgeowlxuqm ouimgdjxlo jhwttcycwl jbcuioqbsj mdjfikdwix jhvdpuxfil peekycgxco sbvxszools xuuqebcrzp jsciwvdqzl obblxzjhco ptobhnpfpo muizaqtpgx jtgjnbtzcl sivwidaszs
样例输出 3
First