Help Please-Lucky Number Game Problem
closed account (DoGTpfjN)
Can somebody help me in this question.
Bob and Alice are playing a game with the following rules:
Initially, they have an integer sequence A1,A2,…,AN; 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 A1,A2,…,AN.
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≤T≤10
1≤N≤2⋅105
1≤a,b≤100
1≤Ai≤109 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.
I cannot figure out what's wrong in my approach.
Please help.
Bob and Alice are playing a game with the following rules:
Initially, they have an integer sequence A1,A2,…,AN; 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 A1,A2,…,AN.
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≤T≤10
1≤N≤2⋅105
1≤a,b≤100
1≤Ai≤109 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.
I cannot figure out what's wrong in my approach.
Please help.
Last edited on
| I cannot figure out what's wrong in my approach. |
What is your approach? Can't know what's wrong with your approach when we don't know what your approach even is.. right?
well this is your first post i see.
u must ask what problem u are having with the problem and leave a link to the problem instead of pasting the whole problem.
if u tell your approach maybe we could help you with where u are going wrong
u must ask what problem u are having with the problem and leave a link to the problem instead of pasting the whole problem.
if u tell your approach maybe we could help you with where u are going wrong
we have to choose the single number in each turn or can choose many numbers in each turn ??
as am i doing by choosing multiples of that number and delete them getting only 18 points
as am i doing by choosing multiples of that number and delete them getting only 18 points
You must remove a non-zero number of numbers, do yes, you can remove more than one.
<vader>
I sense a presence in the source, a feeling that I've seen this problem before....
</vader>
http://www.cplusplus.com/forum/beginner/248547/
I sense a presence in the source, a feeling that I've seen this problem before....
</vader>
http://www.cplusplus.com/forum/beginner/248547/
Topic archived. No new replies allowed.