Page Contents
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
- Airline Restrictions
- Travel Pass
- Shuffling Parities
- XOR Equal
- 2-D Point Meeting
- Minimize Digit Sum
- Minimum Digit Sum 2
- Treasure Hunt
- Covaxin vs Covishield
February Long Challenge 2021
- Frog Sort Solution Codechef
- Chef and Meetings Solution Codechef
- Maximise Function Solution Codechef
- Highest Divisor Solution Codechef
- Cut the Cake Challenge Solution Codechef
- Dream and the Multiverse Solution Codechef
- Cell Shell Solution Codechef
- Multiple Games Solution Codechef
- Another Tree with Number Theory Solution Codechef
- XOR Sums Solution Codechef
- Prime Game Solution CodeChef
- Team Name Solution Codechef
- Bash Matrix Solution CodeChef