No.3140 Weird Parentheses Game
Problem Statement
Definition of a balanced parentheses sequence
A string $X$ is called a balanced parentheses sequence if it satisfies the following.
- $X$ can be turned into the empty string by repeating, $0$ or more times, the operation of deleting a
()contained in $X$ as a contiguous substring
For example, ()(()) and ()()()() are balanced parentheses sequences, but ))(( and )()()( are not balanced parentheses sequences.
There is a balanced parentheses sequence $S$ of length $N$.
First-kun and Second-kun will now play a game using $S$. The game proceeds as follows, with First-kun moving first.
- The player whose turn it is chooses one (non-empty) contiguous substring of $S$ that is a balanced parentheses sequence and deletes it
- If no operation can be performed, the game ends and the player who performed the last operation wins
Determine which player wins when both players play optimally to win.
Input
$N$ $S$
- $1\leq N\leq 1000$
- $S$ is a balanced parentheses sequence of length $N$
Output
Print First on one line if First-kun wins, or Second if Second-kun wins.
The judge requires an exact match. For example, first or SECOND will not be accepted as AC even if the answer is correct.
Print a newline at the end.
Sample
Sample 1
Input
6 ()(())
Output
First
For example, the game may proceed as follows.
- First-kun chooses the $4$-th through $5$-th characters of $S$. $S$ becomes
()() - Second-kun chooses the $1$-st through $2$-nd characters of $S$. $S$ becomes
() - First-kun chooses the $1$-st through $2$-nd characters of $S$. $S$ becomes the empty string
- Second-kun cannot perform an operation, so the game ends and First-kun, who performed the last operation, wins
In this example, the players are not necessarily playing optimally, but First-kun wins even if both play optimally. Therefore, print First.
Sample 2
Input
2 ()
Output
First
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
nauclhlt