# Lucky Number Game | codechef solution

Problem

###Read problem statements in HindiBengaliMandarin ChineseRussian, and Vietnamese as well.

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

• Initially, they have an integer sequence ${�}_{1},{�}_{2},\dots ,{�}_{�}$; 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 ${�}_{1},{�}_{2},\dots ,{�}_{�}$.

### 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 �\le 10$
• $1\le �\le 2\cdot 1{0}^{5}$
• $1\le �,�\le 100$
• $1\le {�}_{�}\le 1{0}^{9}$ for each valid $�$

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

Code(C++) :-

#include <iostream>
using namespace std;

int main() {
int t;
cin>>t;
while(t--)
{
int n,a,b;
cin>>n>>a>>b;
int e,both=0,bob=0,alice=0;
for(int i=0;i<n;i++)
{
cin>>e;
if(e%a==0 && e%b==0)
both++;
else if(e%a==0)
bob++;
else if(e%b==0)
alice++;

}
if(both>0)
bob++;
if(bob>alice)
cout<<"BOB"<<endl;
else
cout<<"ALICE"<<endl;

}
return 0;
}

Code(JAVA):-

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc=new Scanner(System.in);
int t;
t=sc.nextInt();
while(t!=0)
{
int n,a,b;
n=sc.nextInt();
a=sc.nextInt();
b=sc.nextInt();
int e,bob=0,alice=0,both=0;
for(int i=0;i<n;i++)
{
e=sc.nextInt();
if(e%a==0 && e%b==0)
both++;
else if(e%a==0)
bob++;
else if(e%b==0)
alice++;
}
if(both>0)
bob++;
if(bob>alice)
System.out.println("BOB");
else
System.out.println("ALICE");
t--;

}
}
}

### Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-
iMocha coding Questions:-
Tech Mahindra coding questions:-
Unthinkable Solutions coding questions:-