Alice and Bob are employees of Dunder Mifflin. They are playing a game with a binary string of length N. Alice always goes first, followed by Bob, and they take turns making moves.
Game Rules:
On each turn, the player must place either a "&" (AND) or "|" (OR) between two adjacent characters in the string. The final expression is evaluated from left to right, following the placement of operators. Alice wins if the final result is 1, and Bob wins if the final result is 0. Both play optimally, meaning they make moves to maximize their chances of winning. Given the binary string S, determine who will win the game.
Note: The output will be evaluated in the following way: example string : 1010 after sample operations: 1 & 0 | 1 & 0 evaluation: (((1 & 0)| 1) & 0) = 0
Input Format
First line of input contains T i.e the number of testcases
Next pair of lines contains length of the string N & the string S
Constraints
1<= T <= 100 1<= N <= 10^5
Output Format
Print "ALICE" if alice can win the game or "BOB" of bob can win the game. The game will always have a winner
Sample Input 0
2
3
101
2
00
Sample Output 0
ALICE
BOB
Explanation 0
input 1: Alice will first insert a '|' bitwise operator between the second and third bit and bob will insert an '&' bitwise operator between the first and the second bit, the resultant would be 1 & 0 | 1 = 1 Alice will win
input 2: Bob will win regardless of the operation alice performs
This is the actual question. Asked in yesterday's codeUncode event!
Alice's strategy:
If the last symbol is 1, then Alice could place | before it, making answer 1, so Alice would win.
If the last symbol is 0, then Alice must place | before it, otherwise, Bob could place & before it, making answer 0.
Bob's strategy:
If the last symbol is 0, then Bob could place & before it, making answer 0, so Bob would win.
If the last symbol is 1, then Bob must place & before it, otherwise Alice would place | before it, making answer 1.
We can simulate this process in O(n), in each move deleting the last symbol of string.
Very certain this was originally a codeforces question...
yeah but a slight difference in this problem:
The expression is evaluated in this ways (1 or 0) and 0
But in that question the expression is evaluated as 1 or (0 and 0)
Here is the problem link : 2030C - A TRUE Battle