問題一覧 > 通常問題

No.3140 Weird Parentheses Game

レベル : / AI推定難易度 : 143 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 139
作問者 : nauclhlt / テスター : 👑 p-adic
お気に入りにしたユーザー ProblemId : 12089 / 自分の提出
問題文最終更新日: 2025-05-15 08:29:51
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 467 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。