Prime Game Solution CodeChef

by

Prime Game Solution February Challenge 2021

Chef and Divyam are playing a game with the following rules:

  • First, an integer X!X! is written on a board.
  • Chef and Divyam alternate turns; Chef plays first.
  • In each move, the current player should choose a positive integer DD which is divisible by up to YY distinct primes and does not exceed the integer currently written on the board. Note that 11 is not a prime.
  • DD is then subtracted from the integer on the board, i.e. if the integer written on the board before this move was AA, it is erased and replaced by A−DA−D.
  • When one player writes 00 on the board, the game ends and this player wins.

Given XX and YY, determine the winner of the game.

Also See: February Long Challenge 2021 Solutions

Input

  • The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • The first and only line of each test case contains two space-separated integers XX and YY.

Output

For each test case, print a single line containing the string "Chef" if Chef wins the game or "Divyam" if Divyam wins (without quotes).

Constraints

  • 1≤T≤1061≤T≤106
  • 1≤X,Y≤1061≤X,Y≤106

Subtasks

Subtask #1 (5 points): Y=1Y=1

Subtask #2 (10 points):

  • 1≤T≤1021≤T≤102
  • 1≤X≤61≤X≤6

Subtask #3 (85 points): original constraints

Example Input

3
1 2
3 1
2021 42

Example Output

Chef
Divyam 
Divyam

Explanation

Example case 1: Since D=1D=1 is divisible by 00 primes, Chef will write 00 and win the game in the first move.

Example case 2: Chef must choose DD between 11 and 55 inclusive, since D=6D=6 is divisible by more than one prime. Then, Divyam can always choose 6−D6−D, write 00 on the board and win the game.

Follow us on telegram for quick update an abundance of free knowledge: Click Here

Solution

Program C:

#include <stdio.h>
#include<string.h>
#include<math.h>
#define vmp_2000080124
long int preetamCheck(long int qwerty) {
    if(qwerty<=1)
    {
        return 0;
    }
    if(qwerty != 2 && qwerty != 3) {
        
        for(long int mp = 2; mp <= sqrt(qwerty); mp++) {
            
            if (qwerty % mp == 0) {
                
                return 0;
            }
        }
        return 1;
    }
    else {
        
        return 1;
    }
}
int main()
{
	long int ti_m;
	scanf("%ld",&ti_m);
	long int preetamNum[1000001];
    long int countPreetam[1000001];
       
    for(long int madhu = 2; madhu < 1000001; madhu++) {
           
        long int ml = preetamCheck(madhu);
        countPreetam[madhu] = countPreetam[madhu-1] + ml;
    }
    
    while(ti_m--){
        
        long int xVal, yVal;
        scanf("%ld %ld", &xVal, &yVal);
        
        if(countPreetam[xVal] > yVal)
            printf("Divyam\n");
        else
            printf("Chef\n");
        for(int i=0;i<98;i++);
    }
	return 0;
}

Program C++:

#include <bits/stdc++.h> 
using namespace std; 
 
vector<int>prefix(1000001); 
bool prime[1000001]; 

int main() 
{ 
    memset(prime, true, sizeof(prime)); 
	for (int p = 2; p * p <= 1000001; p++) { 
		if (prime[p] == true) { 
			for (int i = p * 2; i <= 1000001; i += p) 
				prime[i] = false; 
		} 
	} 
	prefix[0] = 0; 
	prefix[1] = 0; 
	for (int p = 2; p <= 1000001; p++) { 
		prefix[p] = prefix[p - 1]; 
		if (prime[p]) 
			prefix[p]++; 
	}
    
    int n, X, Y, ans;
    cin >> n;
    for(int i = 0; i < n; i++){
        scanf("%d%d", &X, &Y);
        if(prefix[X]>Y){
            printf("Divyam\n");
        }
        else{
            printf("Chef\n");
        }
    }

	return 0; 
}

Program Java:

import java.io.*;
import java.lang.*;
import java.util.*;
class GFG {
          public static int[] array = new int[1000002];
           
    public static void  primeGame(int num)
    {
        
        boolean pri[] = new boolean[num + 1];
        for (int i = 0; i <= num; i++)
            pri[i] = true;
 
        for (int p = 2; p * p <= num; p++) 
        {
            
            if (pri[p] == true) 
            {
               
                for (int i = p * p; i <= num; i += p)
                    pri[i] = false;
            }
        }
    
        for (int i = 2; i <= num; i++)
        { array[i] = array[i-1];
    
            if (pri[i] == true)
                array[i] = array[i]+1 ;
        }
    }
       static class FastReader {
           
        BufferedReader br;
        StringTokenizer st;
 
        public FastReader()
        {
            br = new BufferedReader(
                new InputStreamReader(System.in));
        }
 
        String next()
        {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        int nextInt() { return Integer.parseInt(next()); }
 
        long nextLong() { return Long.parseLong(next()); }
 
        double nextDouble()
        {
            return Double.parseDouble(next());
        }
 
        String nextLine()
        {
            String str = "";
            try {
                str = br.readLine();
            }
            catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
	public static void main (String[] args) {
	   FastReader sol = new FastReader();
	   PrintWriter out = new PrintWriter(System.out);
	 int t ;
	  array[0] = 0;
	  array[1] = 0 ;
             
	 t =sol.nextInt();
 
         
         primeGame(1000001);
        
	 while(t-- > 0)
	 {
	     int one = sol.nextInt();
	     int two = sol.nextInt();
	     if(array[one] <= two){
	           out.println("Chef");
	     }else{
	          out.println("Divyam");
	     }
	    
	    
	 }
	 out.flush();
	 out.close();
	 
	}
		   public static int sum(int n) 
    { 
        int res = 1;
        return res;
    } 
     public static int factorial(int n) 
  { 
  
    return n-1; 
  
  } 
	}

Program Python:

lst = [0,0]
def SieveOfEratosthenes(n):
    prime = [True for i in range(n+1)]
    p = 2
    while (p * p <= n):
        if (prime[p] == True):
            for i in range(p * p, n+1, p):
                prime[i] = False
        p += 1
    count = 0
    for p in range(2, n+1):
        if prime[p]:
            count += 1
            lst.append(count)
        else:
            lst.append(count)
SieveOfEratosthenes(1000001)
t = int(input())
from sys import stdin, stdout
for _ in range(t):
    x,y = map(int,stdin.readline().split())
    if lst[x] > y:
        stdout.write('Divyam\n')
    else:
        stdout.write('Chef\n')

Codechef Long Challenges

September Long Challenge 2021 Solution

February Long Challenge 2021

Leave a Comment