Alice and Bob's Silly Game


Problem Statement :


Alice and Bob invented the following silly game:

The game starts with an integer, , that's used to build a  of  distinct integers in the inclusive range from  to  (i.e., ).
Alice always plays first, and the two players move in alternating turns.
During each move, the current player chooses a prime number, , from . The player then removes  and all of its multiples from .
The first player to be unable to make a move loses the game.
Alice and Bob play  games. Given the value of  for each game, print the name of the game's winner on a new line. If Alice wins, print Alice; otherwise, print Bob.

Note: Each player always plays optimally, meaning they will not make a move that causes them to lose the game if some better, winning move exists.


Input Format

The first line contains an integer, , denoting the number of games Alice and Bob play.
Each line  of the  subsequent lines contains a single integer, , describing a game.

Output Format

For each game, print the name of the winner on a new line. If Alice wins, print Alice; otherwise, print Bob.



Solution :


                        In  C  :





#include <stdio.h>

int main(void) {
	
	int t;scanf("%d",&t);
	while(t--)
	{
	    int i,j;
	    int n;scanf("%d",&n);
    	int arr[100005];
    	for(i=1;i<=100000;i++)
    	arr[i]=1;
    	
    	for(i=2;i<=100000;i++)
    	{
    	    if(arr[i]==1)
    	    {
    	        for(j=2*i;j<=100000;j+=i)
    	        arr[j]=0;
    	    }
    	}
    	arr[1]=0;
    	int c=0;
    	for(i=1;i<=n;i++)
    	if(arr[i]==1)
    	c++;
    	if(c%2==0)
    	printf("Bob\n");
    	else
    	printf("Alice\n");
	}
	
	return 0;
}
                    

                        In  C++ :





#include <bits/stdc++.h>

using namespace std;

int N;
int pr[100001];

int main()
{
    scanf("%d", &N);
    for(int i=2; i<=100000; i++)
        pr[i]=1;
    for(int i=2; i<=100000; i++) if(pr[i])
        for(int j=i*2; j<=100000; j+=i)
            pr[j]=0;
    for(int i=3; i<=100000; i++)
        pr[i]^=pr[i-1];
    while(N--)
    {
        int x;
        scanf("%d", &x);
        if(pr[x])
            printf("Alice\n");
        else
            printf("Bob\n");
    }
    return 0;
}
                    

                        In  Java :







import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        ArrayList<Integer> primes = new ArrayList<Integer>();
        primes.add(2);
        for (int i = 3; i <= 100000; i+=2) {
            int sqrt = (int)Math.sqrt(i);
            boolean prime = true;
            for (int p : primes) {
                if (p > sqrt)
                    break;
                if (i%p==0) {
                    prime = false;
                    break;
                }
            }
            if (prime)
                primes.add(i);
        }
        int[] counts = new int[100001];
        int currIndex = 0;
        for (int i = 0; i <= 100000; i++) {
            if (currIndex < primes.size() && primes.get(currIndex) == i)
                currIndex++;
            counts[i] = currIndex;
        }
        int g = sc.nextInt();
        for (int i = 0; i < g; i++) {
            System.out.println(counts[sc.nextInt()]%2==0?"Bob":"Alice");
        }
    }
}
                    

                        In  Python3 :





#!/bin/python3

import sys

prime_pre = [0 for i in range(100001)]
sieve = [0 for i in range(100001)]
for i in range(2, 100000):
    if sieve[i] == 0:
        prime_pre[i] = prime_pre[i-1]+1
        #primes.append(i)
        for j in range(i, 100001, i):
            sieve[j] = i
    else:
        prime_pre[i] = prime_pre[i-1]


g = int(input().strip())
for a0 in range(g):
    n = int(input().strip())
    # your code goes here
    print("Bob" if prime_pre[n]%2 == 0 else "Alice")
                    



Copyrights © ClownMonster's Inc