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 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 $N$, $a$ 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 ### 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.
|Tags||game-theory, hruday968, jan19, maths, simple, taran_1407|
|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|
Fetching successful submissions
If you are still having problems, see a sample solution here.