Bob and Alice are playing a game with the following rules:
- Initially, they have an integer sequence ; in addition, Bob has a lucky number and Alice has a lucky number .
- The players alternate turns. In each turn, the current player must remove a non-zero number of elements from the sequence; each removed element should be a multiple of the lucky number of this player.
- If it is impossible to remove any elements, the current player loses the game.
It is clear that one player wins the game after a finite number of turns. Find the winner of the game if Bob plays first and both Bob and Alice play optimally.
Input
- The first line of the input contains a single integer denoting the number of test cases. The description of test cases follows.
- The first line of each test case contains three space-separated integers , and .
- The second line contains space-separated integers .
Output
For each test case, print a single line containing the string "ALICE"
if the winner is Alice or "BOB"
if the winner is Bob (without quotes).
Constraints
- for each valid
Subtasks
Subtask #1 (18 points):
Subtask #2 (82 points): original constraints
Sample 1:
Input
Output
2 5 3 2 1 2 3 4 5 5 2 4 1 2 3 4 5
ALICE BOB
Explanation:
Example case 1: Bob removes and the sequence becomes . Then, Alice removes and the sequence becomes . Now, Bob is left with no moves, so Alice is the winner.
Solution
- If contains elements which are divisible by both and , It is optimal for Bob to delete all such elements in the very first move. Turn goes to Alice.
- Now, it is optimal for both players to remove exactly one number they can remove, until one of the players is unable to make a move, thus losing the game. The number of moves Bob can make is Number of elements divisible by after deleting numbers divisible by both and . Same way for Alice.
0 Comments
If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.