Header Ads Widget

Lucky Number Game | codechef solution

Rajnish Tripathi 14:41

Problem

###Read problem statements in Hindi, Bengali, Mandarin Chinese, Russian, and Vietnamese as well.

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

  • Initially, they have an integer sequence �1,�2,…,��; 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,…,��.

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≤�≤10
  • 1≤�≤2⋅105
  • 1≤�,�≤100
  • 1≤��≤109 for each valid �

Subtasks

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 [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.


Code(C++) :-

#include <iostream>
using namespace std;

int main() {
  // your code goes here
  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
    {
        // your code goes here
        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:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-


Tags:

Post a Comment

0 Comments