No.973 余興

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 53
作問者 :

沙耶花 / テスター :

shibh308

5 ProblemId : 3636 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2020-08-17 15:49:50

問題文

AさんとBさんがパーティーを開きました.
彼女たちはパーティー会場前方にあるステージに立っていて,その目の前には左右に長いテーブルがあります.

テーブル上には $N$ 個のシュークリームが一列に並べられています.
(ステージから見て)左から $i$ 番目のシュークリームの栄養価は $a_{i}$ キロカロリーです.

彼女たちはパーティーの余興としてゲームをすることにしました.
ゲームはAさんから始めて,交互に次の操作のうち一方を選んで行います.

(ステージから見て)左端にあるシュークリームを含む,位置が連続した1個以上のシュークリームを食べる
(ステージから見て)右端にあるシュークリームを含む,位置が連続した1個以上のシュークリームを食べる

ただし,シュークリームを中途半端に(たとえば,1個と半分だけ)食べることはできません.

また,彼女たちの間では,「一度に

X

キロカロリーを超える栄養を摂ると太る」という噂が信じられています.
彼女たちはダイエットに命をかけているため,
自分が操作をする番1回の間において食べるシュークリームの栄養価の合計が

X

キロカロリーを超えることが無いようにします.

最後にシュークリームを食べた人が敗者となり,パーティーの開催費用を支払うことになります.
彼女たちが勝利を目的に最適に行動した場合,どちらが勝者となるかを判定してください.

入力

 $N X$ 
 $a_{1} a_{2} . . . a_{N}$

$1 \leq N \leq 5000$
$1 \leq X \leq 10^{9}$
$1 \leq a_{i} \leq X$
入力はすべて整数

出力

Aさんが勝つ場合は"A"と,Bさんが勝つ場合は"B"と出力してください.
最後に改行してください.

サンプル

サンプル1

入力

3 3
1 2 3

出力

最初にAさんが左端にあるシュークリームを含む2個のシュークリームを食べた場合,
Bさんが必ず最後の一個を食べることになります.

サンプル2

入力

1 100
100

出力

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