No.1267 Stop and Coin Game
タグ : / 解いたユーザー数 165
作問者 : stoq / テスター : momohara
問題文
暇を持て余した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もしくは右上の雲マークをクリックしてアカウントを作成してください。