No.582 Candy Box 3
タグ : / 解いたユーザー数 191
作問者 :
nmnmnmnmnmnmnm
/ テスター :
mai
Problem Statement
There are $N$ boxes that can hold candies.
The $i$-th box contains $C_i$ candies.
A and B play a game with the following rules.
・A moves first, and A and B take turns alternately.
・In one move, A chooses any one box of candies and takes 1 candy from it.
・In one move, B chooses any one box of candies and takes 1 or 2 candies from it.
・Neither A nor B may pass their move.
・The player who cannot take a candy because all the boxes are empty loses.
・Both A and B play optimally to win.
Given the initial state, determine who wins in the end.
Input
$N$ $C_1$ $C_2$ $\dots$ $C_N$
$N$ is the number of candy boxes. $1 \le N\le 150$.
$C_i$ is the number of candies initially in the $i$-th box. $0 \le C_i\le 1000000000=10^9$.
Output
Print "A" if A wins, and "B" if B wins.
Print a newline at the end.
Sample
Sample 1
Input
2 1 2
Output
A
There are 2 candy boxes.
One box contains 1 candy.
The other box contains 2 candies.
A, moving first, takes 1 candy from the box containing 2 candies.
B takes 1 candy from either box.
A takes 1 candy from the box that still has a candy.
All the boxes are now empty, and B cannot take a candy.
Therefore, A wins.
Sample 2
Input
1 3
Output
B
There is 1 candy box.
The box contains 3 candies.
A takes 1 candy from the box.
B takes 2 candies from the box.
The box is now empty, and A cannot take a candy.
Therefore, B wins.
Sample 3
Input
5 1 1 2 4 0
Output
B
B wins.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。