No.1267 Stop and Coin Game
Problem Statement
With time on their hands, stop-kun and stoq-kun decided to play a game.
There is a glass containing water and $N$ coins. The remaining capacity of the glass is $V$ mL, and the volume of the $i$-th coin is $A_i$ mL.
Starting with stop-kun, the two players take turns choosing one coin that has not been chosen yet and putting it into the glass.
If a coin of volume $y$ mL is put in when the remaining capacity of the glass is $x$ mL, the remaining capacity becomes $x-y$ mL. The glass is large enough that a coin can always be put in.
If putting in a coin makes the water overflow from the glass, that is, the remaining capacity becomes negative, the player who put in that coin loses and the other player wins.
If the water has not overflowed by the end, the game is a draw.
When both players act optimally, print First if the first player wins, Second if the second player wins, and Draw if the game is a draw.
Input
$N\ V$ $A_1 \dots A_N$
- All inputs are integers.
- $1 \leq N \leq 20$
- $1 \leq V \leq 10^{15}$
- $1 \leq A_i \leq 10^{12}$
Output
When both players act optimally, print First if the first player wins, Second if the second player wins, and Draw if the game is a draw.
Sample
Sample 1
Input
3 5 5 1 1
Output
First
If the first player chooses the coin of volume $5$ mL, the remaining capacity of the glass becomes exactly $0$ mL, and the second player loses no matter which coin they choose.
Sample 2
Input
3 100 1 2 3
Output
Draw
No matter how the players act, the water never overflows from the glass, so the game is a draw.
Sample 3
Input
1 1 1000000000000
Output
Second
The only remaining coin has volume $1000000000000$ mL and the remaining capacity of the glass is $1$ mL, so the first player loses.
Sample 4
Input
6 10 1 2 3 4 5 6
Output
First
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
stoq
momohara