問題一覧 > 通常問題

No.2823 PEX (Predecessing Excluded Value) Game

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

問題文

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

集合 SS があり、はじめ S=[L1,R1][L2,R2][LN,RN]S = [L_1, R_1] \cup [L_2, R_2] \cup \cdots \cup [L_N, R_N] です。

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

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

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

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

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

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

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

入力

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

NN
L1R1L_1 \enspace R_1
L2R2L_2 \enspace R_2
\vdots
LNRNL_N \enspace R_N

出力

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

制約

  • 1N3×1051 \leq N \leq 3 \times 10^5
  • 0<L1R1<L2R2<<LNRN<2600 < 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}S = \{\, 1, 2, 3, 5, 6 \,\} です。
先手の first くんが x=6x = 6 として 11 回操作を行うと、S={1,2,3,4,5}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もしくは右上の雲マークをクリックしてアカウントを作成してください。