実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 600 点
問題文
小石の山が N 個あります.最初,i 番目の山には A_i 個の小石があります.
これらを用いて,高橋君と青木君がゲームをします. 高橋君から始めて,交互に次の操作を行い,操作を行えなくなった方が負けとなります.
- 山を 1 つ以上選び,選んだそれぞれの山から,高橋君の操作の場合は X 個ずつ,青木君の操作の場合は Y 個ずつ小石を取り除く. ただし,小石の個数が足りない山を選ぶことはできない.
二人が最適に行動したとき,どちらがゲームに勝つかを求めてください.
制約
- 1 \leq N \leq 2\times 10^5
- 1 \leq X, Y \leq 10^9
- 1 \leq A_i \leq 10^9
入力
入力は以下の形式で標準入力から与えられる.
N X Y A_1 A_2 \cdots A_N
出力
このゲームに勝つのが高橋君の場合 First
を,青木君の場合 Second
を出力せよ.
入力例 1
2 1 1 3 3
出力例 1
First
例えば,以下のようなゲームの進行が考えられます.
- 高橋君が両方の山から石を 1 つ取り除く.
- 青木君が 1 番目の山から石を 1 つ取り除く.
- 高橋君が 1 番目の山から石を 1 つ取り除く.
- 青木君が 2 番目の山から石を 1 つ取り除く.
- 高橋君が 2 番目の山から石を 1 つ取り除く.
青木君がどのように操作を行っても高橋君が勝つことができるので,答えは First
です.
入力例 2
2 1 2 3 3
出力例 2
Second
Score : 600 points
Problem Statement
There are N piles of pebbles. Initially, the i-th pile has A_i pebbles.
Takahashi and Aoki will play a game using these piles. They will alternately perform the following operation, with Takahashi going first, and the one who becomes unable to do so loses the game.
- Choose one or more piles, and remove the following number of pebbles from each chosen pile: X pebbles if this operation is performed by Takahashi, and Y pebbles if performed by Aoki. Here, a pile with an insufficient number of pebbles cannot be chosen.
Determine the winner of the game if both players play optimally.
Constraints
- 1 \leq N \leq 2\times 10^5
- 1 \leq X, Y \leq 10^9
- 1 \leq A_i \leq 10^9
Input
Input is given from Standard Input in the following format:
N X Y A_1 A_2 \cdots A_N
Output
If it is Takahashi who will win the game, print First
; if it is Aoki, print Second
.
Sample Input 1
2 1 1 3 3
Sample Output 1
First
Here is one possible progression of the game.
- Takahashi removes 1 pebble from both piles.
- Aoki removes 1 pebble from the 1-st pile.
- Takahashi removes 1 pebble from the 1-st pile.
- Aoki removes 1 pebble from the 2-nd pile.
- Takahashi removes 1 pebble from the 2-nd pile.
No matter how Aoki plays, Takahashi can always win, so the answer is First
.
Sample Input 2
2 1 2 3 3
Sample Output 2
Second