問題一覧 > 通常問題

No.1267 Stop and Coin Game

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 130
作問者 : 👑 stoqstoq / テスター : momoharamomohara
7 ProblemId : 5365 / 出題時の順位表
問題文最終更新日: 2020-10-17 12:32:25

問題文

暇を持て余したstopくんとstoqくんは、ゲームをして遊ぶことにしました。

水の入ったグラスと $N$ 枚の硬貨があります。グラスの残り容量は $V$ mL、$i$ 枚目の硬貨の体積は $A_i$ mLです。

stopくんから始めて交互に、まだ選ばれていない硬貨を1枚選んでグラスに入れていきます。 グラスの残り容量が $x$ mLのときに体積 $y$ mLの硬貨を入れると、残り容量は $x-y$ mLになります。グラスは十分大きいので硬貨が入らないということはありません。
硬貨を入れてグラスから水が溢れる、すなわち残り容量が負になるとその硬貨を入れた人が敗北し、そうでない人の勝利となります。 最後まで水が溢れなかった場合は引き分けです。

両者が最適に行動したとき、先手が勝つならFirst、後手が勝つならSecond、引き分けならDrawを出力してください。

入力

$N\ V$
$A_1 \dots A_N$

  • 入力は全て整数
  • $1 \leq N \leq 20$
  • $1 \leq V \leq 10^{15}$
  • $1 \leq A_i \leq 10^{12}$

出力

両者が最適に行動したとき、先手が勝つならFirst、後手が勝つならSecond、引き分けならDrawを出力してください。

サンプル

サンプル1
入力
3 5
5 1 1
出力
First

先手が体積 $5$ mLの硬貨を選ぶとグラスの残り容量はちょうど $0$ mLになり、後手はどの硬貨を選んでも敗北します。

サンプル2
入力
3 100
1 2 3
出力
Draw

両者がどのように行動してもグラスから水が溢れることはなく、引き分けとなります。

サンプル3
入力
1 1
1000000000000
出力
Second

残りの硬貨は体積 $1000000000000$ mLのものだけで、グラスの残り容量は $1$ mLなので先手の負けです。

サンプル4
入力
6 10
1 2 3 4 5 6
出力
First

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。