No.3342 AAB Game
タグ : / 解いたユーザー数 28
作問者 :
hir355
/ テスター :
noya2
Problem Statement
A string consisting of $0$ or more As followed by $1$ B, in this order, is called an AAB string.
For example, AAB and B are AAB strings. AABB and A are not AAB strings.
You are given a string $S$ of length $N$ consisting of A and B.
Let $S[i,j]$ denote the substring of $S$ from the $i$-th character through the $j$-th character.
- Starting with Alice, the two players take turns alternately.
- On each turn, the player chooses $i,j \ (1 \leq i \leq j \leq N)$ such that $S[i,j]$ is an AAB string, and for each character in $S[i,j]$, replaces it with
Bif it isA, and withAif it isB.
It can be proved that this game always ends in a finite number of turns. Determine which player wins when both players play optimally.
Constraints
- $1 \leq N \leq 2 \times 10^5$
- $S$ is a string of length $N$ consisting of
AandB - $N$ is an integer
Input
The input is given from standard input in the following format.
$N$ $S$
Output
Print Alice if Alice wins when both players play optimally, and Bob if Bob wins.
Sample
Sample 1
Input
2 AB
Output
Alice
On the first turn, Alice can change $S$ to BA or AA.
Sample 2
Input
3 ABB
Output
Bob
Sample 3
Input
5 BABAB
Output
Bob
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。