No.2823 PEX (Predecessing Excluded Value) Game
タグ : / 解いたユーザー数 21
作問者 :
みどりむし🦠
/ テスター :
FplusFplusF
Problem Statement
All alone together, first-kun and second-kun are playing a two-player game.
There is a set $S$, and initially $S = [L_1, R_1] \cup [L_2, R_2] \cup \cdots \cup [L_N, R_N]$.
- Here, for any $2$ integers $l, r$, $[l, r]$ denotes the set consisting of all integers satisfying $l \leq x \leq r$.
A player can perform the following operation:
- First, freely choose $1$ integer $x$ such that $x \in S$.
- Next, consider the largest integer $x'$ such that $1 \leq x' < x$ and $x' \not \in S$:
- If such an $x'$ exists, remove $x$ from $S$ and newly insert $x'$ into $S$.
- If no such $x'$ exists, the player who attempted the operation explodes.
The players, first-kun and second-kun, take turns repeatedly performing the above operation, with first-kun going first.
On their turn, each player must perform the operation exactly $1$ time.
The player who explodes first loses, and the other player wins.
When both players play optimally, which player wins?
Determine the winner.
Note that under the constraints of this problem, the game is always decided after a finite number of operations.
Input
The input is given from standard input in the following format:
$N$ $L_1 \enspace R_1$ $L_2 \enspace R_2$ $\vdots$ $L_N \enspace R_N$
Output
When the $2$ players both play optimally, print First if first-kun wins, or Second if second-kun wins, on one line to standard output.
Constraints
- $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}$
- All input values are integers.
Sample
Sample Input/Output 1
Input
2 1 3 5 6
Output
First
Initially, $S = \{\, 1, 2, 3, 5, 6 \,\}$.
If first-kun, who moves first, performs the operation $1$ time with $x = 6$, then $S = \{\, 1, 2, 3, 4, 5 \,\}$, and in this state second-kun, who moves second, explodes no matter what operation he performs.
Therefore, print First.
Sample Input/Output 2
Input
3 1 100 101 200 201 300
Output
Second
Sample Input/Output 3
Input
3 14 15 92 6535 8979 32384
Output
First
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。