Lucky Number Game

All submissions for this problem are available.
###Read problem statements in [Hindi](http://www.codechef.com/download/translated/JAN19/hindi/HP18.pdf), [Bengali](http://www.codechef.com/download/translated/JAN19/bengali/HP18.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/JAN19/mandarin/HP18.pdf), [Russian](http://www.codechef.com/download/translated/JAN19/russian/HP18.pdf), and [Vietnamese](http://www.codechef.com/download/translated/JAN19/vietnamese/HP18.pdf) as well. 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 nonzero 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 spaceseparated integers $N$, $a$ and $b$.  The second line contains $N$ spaceseparated 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 ### Example Input ``` 2 5 3 2 1 2 3 4 5 5 2 4 1 2 3 4 5 ``` ### Example Output ``` 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.Author:  hruday968 
Editorial  https://discuss.codechef.com/problems/HP18 
Tags  gametheory, hruday968, jan19, maths, simple, taran_1407 
Date Added:  11122018 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions