No.973 Party Entertainment
沙耶花
shibh308Problem Statement
A and B held a party.
They are standing on the stage at the front of the party venue, and right in front of them is a table that is long from left to right.
On the table, $N$ cream puffs are arranged in a row.
The $i$-th cream puff from the left (as seen from the stage) has a nutritional value of $a_i$ kilocalories.
They decided to play a game as entertainment for the party.
Starting with A, they take turns choosing and performing one of the following operations.
- Eat one or more cream puffs in consecutive positions, including the cream puff at the left end (as seen from the stage)
- Eat one or more cream puffs in consecutive positions, including the cream puff at the right end (as seen from the stage)
Also, they believe a rumor that "taking in more than $X$ kilocalories of nutrition at one time makes you fat."
Since they are devoting their lives to dieting,
they make sure that the total nutritional value of the cream puffs eaten during a single turn of their own never exceeds $X$ kilocalories.
The person who eats the last cream puff loses and has to pay the cost of holding the party.
Determine who wins when both of them act optimally with the aim of winning.
Input
$N\ X$ $a_1\ a_2\ ...\ a_N$
- $1 \le N \le 5000$
- $1 \le X \le 10^9$
- $ 1 \le a_i \le X$
- All inputs are integers
Output
Print "A" if A wins, and "B" if B wins.
Print a newline at the end.
Sample
Sample 1
Input
3 3 1 2 3
Output
A
If A first eats the 2 cream puffs including the one at the left end,
B will inevitably eat the last one.
Sample 2
Input
1 100 100
Output
B
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。