問題一覧 > 通常問題

No.1267 Stop and Coin Game

レベル : / AI推定難易度 : 1200 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 173
作問者 : stoq / テスター : momohara
お気に入りにしたユーザー ProblemId : 5365 / 自分の提出
問題文最終更新日: 2020-10-17 12:32:25
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 271 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。