102976: [Atcoder]ABC297 G - Constrained Nim 2
Description
Score : $600$ points
Problem Statement
There are $N$ piles of stones. Initially, the $i$-th pile contains $A_i$ stones. With these piles, Taro the First and Jiro the Second play a game against each other.
Taro the First and Jiro the Second make the following move alternately, with Taro the First going first:
- Choose a pile of stones, and remove between $L$ and $R$ stones (inclusive) from it.
A player who is unable to make a move loses, and the other player wins. Who wins if they optimally play to win?
Constraints
- $1\leq N \leq 2\times 10^5$
- $1\leq L \leq R \leq 10^9$
- $1\leq A_i \leq 10^9$
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
$N$ $L$ $R$ $A_1$ $A_2$ $\ldots$ $A_N$
Output
Print First
if Taro the First wins; print Second
if Jiro the Second wins.
Sample Input 1
3 1 2 2 3 3
Sample Output 1
First
Taro the First can always win by removing two stones from the first pile in his first move.
Sample Input 2
5 1 1 3 1 4 1 5
Sample Output 2
Second
Sample Input 3
7 3 14 10 20 30 40 50 60 70
Sample Output 3
First
Input
题意翻译
给定 $n$ 堆喵喵,你(`First`)和 lbw(`Second`) 轮流吃,每次可以吃掉 $l \sim r$ 个喵喵。谁不能吃喵喵了谁就输了。问谁会赢?Output
分数:600分
问题描述
有N堆石头。最初,第i堆包含Ai个石头。用这些石头,大郎和次郎轮流进行游戏。
大郎和次郎轮流进行以下操作,大郎先进行:
- 选择一堆石头,从中移除L到R(含)个石头。
无法进行操作的玩家输掉游戏,另一名玩家获胜。如果他们优化操作以求获胜,谁会赢呢?
约束
- $1\leq N \leq 2\times 10^5$
- $1\leq L \leq R \leq 10^9$
- $1\leq A_i \leq 10^9$
- 输入中的所有值都是整数。
输入
输入以标准输入的以下格式给出:
$N$ $L$ $R$ $A_1$ $A_2$ $\ldots$ $A_N$
输出
如果大郎获胜,则打印First
;如果次郎获胜,则打印Second
。
样例输入1
3 1 2 2 3 3
样例输出1
First
大郎总可以在他的第一次操作中从第一堆中移除两个石头来获胜。
样例输入2
5 1 1 3 1 4 1 5
样例输出2
Second
样例输入3
7 3 14 10 20 30 40 50 60 70
样例输出3
First