No.1208 anti primenumber game
タグ : / 解いたユーザー数 96
作問者 :
simasima_71
/ テスター :
kaage
Problem Statement
There are $N$ piles of stones arranged in a row.
The $i$-th pile from the left contains $A_i$ stones.
The first player and the second player alternately take stones according to the rules.
The player with a higher score than the opponent wins.
In case of a tie, the second player wins.
＜Rules＞
A player takes any number of stones, at least $1$, at once from the leftmost pile among the piles that have stones.
However, the number of stones remaining in the pile from which stones were taken must not be a prime number.
A player gets $1$ point for every $1$ stone taken.
Taking the last stone of a pile deducts $M$ points.
Scores can become negative.
Which player wins when both play optimally?
Input
$N\ M$ $A_1\ \dots\ A_N$
All inputs are integers.
$1 \le N \le 200000=2 \times 10^5$
$0 \le M \le 1000000000000=10^{12}$
$1 \le A_i \le 1000000000000=10^{12}$
Note: $A_i$ may be a prime number.
Output
Print First if the first player wins, and Second if the second player wins.
Print a newline at the end.
Sample
Sample 1
Input
3 2 6 3 2
Output
First
Here is one example of how the game may proceed. The moves shown here are not necessarily optimal.
The first player takes $2$ stones from the leftmost pile, gets $2$ points, and leaves $4$ stones in the pile.
The second player takes $4$ stones from the leftmost pile, gets $4$ points, and leaves $0$ stones in the pile.
Since the second player took the last stone of the leftmost pile, $2$ points are deducted from the second player's score.
The first player takes $2$ stones from the second pile from the left, gets $2$ points, and leaves $1$ stone in the pile. This is fine because $1$ is not a prime number.
The second player takes $1$ stone from the second pile from the left, gets $1$ point, and leaves $0$ stones in the pile.
Since the second player took the last stone of the second pile from the left, $2$ points are deducted from the second player's score.
The first player takes $2$ stones from the third pile from the left, gets $2$ points, and leaves $0$ stones in the pile.
Since the first player took the last stone of the third pile from the left, $2$ points are deducted from the first player's score.
In this case, the first player has $4$ points and the second player has $1$ point, so the first player wins.
Sample 2
Input
1 1000000000000 1
Output
Second
The first player has no choice but to take $1$ stone. (Poor thing...)
The score is $-999999999999$ to $0$, so the second player wins.
Sample 3
Input
2 0 1 1
Output
Second
$M$ can be $0$.
The first and second players each take one stone,
and the score is tied at $1$ to $1$, so the second player wins.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。