Lucky Number Game CodeChef Solution | HP18

 

Bob and Alice are playing a game with the following rules:

  • Initially, they have an integer sequence A_1, A_2, \ldots, A_N; in addition, Bob has a lucky number a and Alice has a lucky number b.
  • 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 T denoting the number of test cases. The description of T test cases follows.
  • The first line of each test case contains three space-separated integers Na and b.
  • The second line contains N space-separated integers A_1, A_2, \ldots, A_N.

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

  • 1 \le T \le 10
  • 1 \le N \le 2 \cdot 10^5
  • 1 \le a, b \le 100
  • 1 \le A_i \le 10^9 for each valid i

Subtasks

Subtask #1 (18 points): a = b

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 3 and the sequence becomes [1, 2, 4, 5]. Then, Alice removes 2 and the sequence becomes [1, 4, 5]. Now, Bob is left with no moves, so Alice is the winner.



Solution


  • If A contains elements which are divisible by both a and b, 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 a after deleting numbers divisible by both a and b. Same way for Alice.

Post a Comment

0 Comments