No.2823 PEX (Predecessing Excluded Value) Game
タグ : / 解いたユーザー数 22
作問者 : 🦠みどりむし / テスター : achapi FplusFplusF viral8 👑 AngrySadEight
問題文
ふたりぼっちの 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もしくは右上の雲マークをクリックしてアカウントを作成してください。