問題一覧 > 通常問題

No.2823 PEX (Predecessing Excluded Value) Game

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 22
作問者 : 🦠みどりむし🦠みどりむし / テスター : achapiachapi FplusFplusFFplusFplusF viral8viral8 👑 AngrySadEightAngrySadEight
4 ProblemId : 10092 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-07-29 14:10:14

問題文

ふたりぼっちの first くんと second くんは、対戦ゲームで遊んでいます。

集合 $S$ があり、はじめ $S = [L_1, R_1] \cup [L_2, R_2] \cup \cdots \cup [L_N, R_N]$ です。

  • ここで、任意の $2$ 整数 $l, r$ について、$l \leq x \leq r$ なる整数すべてからなる集合を $[l, r]$ と表します。

プレイヤーは次の操作ができます:

  • はじめに、$x \in S$ なる整数 $x$ を自由に $1$ つ選ぶ。
  • つぎに、$1 \leq x' < x$ かつ $x' \not \in S$ なる最大の整数 $x'$ について、
    • そのような $x'$ が存在するならば、$S$ から $x$ を取り除き、$S$ に $x'$ を新たに挿入する。
    • そのような $x'$ が存在しないならば、操作を行おうとしたプレイヤーは爆発する。

プレイヤーである first くんと second くんは、first くんを先手として、交互に、先述の操作を、繰り返し行います。

二人とも、自身が操作を行う番になったら必ず、ちょうど $1$ 回だけ操作を行わなければなりません。
先に爆発したプレイヤーは負け、もう一方のプレイヤーが勝ちます。

お互いが最善を尽くすとき、どちらのプレイヤーが勝つでしょうか。
判定してください。

なおこのゲームは、この問題の制約のもとで、必ず有限回の操作で勝敗が定まります。

入力

入力は、以下の形式で標準入力より与えられる:

$N$
$L_1 \enspace R_1$
$L_2 \enspace R_2$
$\vdots$
$L_N \enspace R_N$

出力

$2$ 人のプレイヤーが互いに最善を尽くすとき、first くんが勝つならば First、second くんが勝つならば Second と標準出力へ一行に出力せよ。

制約

  • $1 \leq N \leq 3 \times 10^5$
  • $0 < L_1 \leq R_1 < L_2 \leq R_2 < \cdots < L_N \leq R_N < 2^{60}$
  • 入力はすべて整数

サンプル

入出力例1
入力
2
1 3
5 6
出力
First

はじめ、$S = \{\, 1, 2, 3, 5, 6 \,\}$ です。
先手の first くんが $x = 6$ として $1$ 回操作を行うと、$S = \{\, 1, 2, 3, 4, 5 \,\}$ となり、この状態では後手の second 君はどのような操作を行っても爆発してしまいます。
したがって、First と出力します。

入出力例2
入力
3
1 100
101 200
201 300
出力
Second
入出力例3
入力
3
14 15
92 6535
8979 32384
出力
First

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。