No.3090 NimNim
タグ : / 解いたユーザー数 47
作問者 :
yuusaan
/ テスター :
👑 
amentorimaru
Problem Statement
You are given a sequence of positive integers $A_1,A_2,\dots ,A_N$ of length $N$ and a sequence of positive integers $B_1,B_2, \dots ,B_M$ of length $M$. The sequence $A$ as given at this point is called the "initial state".
Yu~san and Osakana-san play a game using these arrays. In the game, the players alternately repeat the following procedure, starting with Yu~san.
- Choose an integer $i$ between $1$ and $N$, inclusive, such that $A_i\ge 1$, and replace $A_i$ with an integer that is at least $0$ and less than $A_i$.
- If all elements of the array $A$ are $0$ immediately after the replacement, return $A$ to the initial state, choose an integer $j$ between $1$ and $M$, inclusive, such that $B_j\ge 1$, and replace $B_j$ with an integer that is at least $0$ and less than $B_j$.
- However, if the array $B$ has no such element at this time, that player loses. The player who did not lose is the winner.
This game always ends with a winner being determined after a finite number of operations, and exactly one of Yu~san and Osakana-san can always win by playing optimally. Determine which one it is.
Input
$N\ M$ $A_1 \ A_2 \ \dots \ A_N$ $B_1 \ B_2 \ \dots \ B_M$
Constraints
- $1\le N,M \le 10^5$
- $1\le A_i,B_j \le 10^6(1\le i \le N,1\le j \le M)$
- All inputs are integers.
Output
Print First on one line if Yu~san is the one who can always win by playing optimally, or Second if it is Osakana-san, followed by a newline.
Sample
Sample 1
Input
1 3 1 2 1 2
Output
First
As an example, the game proceeds as follows.
- Yu~san replaces $A_1$ with $0$. Since all elements of $A$ have become $0$, $A$ is returned to the initial state, and $B_2$ is replaced with $0$.
- Osakana-san replaces $A_1$ with $0$. Since all elements of $A$ have become $0$, $A$ is returned to the initial state, and $B_1$ is replaced with $0$.
- Yu~san replaces $A_1$ with $0$. Since all elements of $A$ have become $0$, $A$ is returned to the initial state, and $B_3$ is replaced with $0$.
- Osakana-san replaces $A_1$ with $0$. Since all elements of $A$ have become $0$, $A$ is returned to the initial state, but since all elements of the array $B$ are $0$, Osakana-san loses and Yu~san wins.
For this input, Yu~san can always win by playing optimally. Therefore, print First.
Sample 2
Input
2 1 2 2 1
Output
Second
As an example, the game proceeds as follows.
- Yu~san replaces $A_1$ with $0$.
- Osakana-san replaces $A_2$ with $0$. Since all elements of $A$ have become $0$, $A$ is returned to the initial state, and $B_1$ is replaced with $0$.
- Yu~san replaces $A_1$ with $1$.
- Osakana-san replaces $A_2$ with $0$.
- Yu~san replaces $A_1$ with $0$. Since all elements of $A$ have become $0$, $A$ is returned to the initial state, but since all elements of the array $B$ are $0$, Yu~san loses and Osakana-san wins.
For this input, Osakana-san can always win by playing optimally. Therefore, print Second.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。