In this HackerEarth Chandu and Chandni problem solution, Chandu and Chandni are playing a game! The game is very similar to the game of chess, But there is only one piece on the board i.e Queen. Also, Queen is allowed to move only towards the top left corner.
For clarification, If Queen is placed at i,j then in a turn queen can move:
  1. Any number of cells leftwards.
  2. Any number of cells upwards.
  3. Any number of cells Diagonally(only N-W direction).
Please note that the board is quarter infinite i.e there is a top left corner but it extends to infinity in the south and east direction.

Rules:
  1. Chandni will always play the first turn.
  2. They both will get alternative turns.
  3. They must move the queen in their turn (No skip option) and that too according to the rule specified above.
  4. Whosoever is unable to make a move loses.
Given The position of the queen on the board(0 indexes based). Print who will win the game.


HackerEarth Chandu and Chandni problem solution


HackerEarth Chandu and Chandni problem solution.

#include<bits/stdc++.h>
using namespace std;

#define st_clk double st=clock();
#define end_clk double en=clock();
#define show_time cout<<"\tTIME="<<(en-st)/CLOCKS_PER_SEC<<endl;


#define f_in(st) freopen(st,"r",stdin);
#define f_out(st) freopen(st,"w",stdout);

#define sc(n) scanf("%d",&n)
#define scs(n) scanf("%s",&n)
#define pr(n) printf("%d\n",n)
#define prs(n) printf("%s\n",n)


int hashTable[1700000];
int countTable = 0;
void process(){
     double phi = (1+sqrt(5))/2.0;
     for(int i=1;i<=500000;i++){
          hashTable[((int)(phi*i))] = int(phi*phi*i);
          countTable = ((int)(phi*i));
     }
}

int main(){
     #ifndef ONLINE_JUDGE
     f_in("in");
     f_out("out");
     #endif
     process();
     cout << countTable << endl;
     int t;
     scanf("%d",&t);
     while(t--){
          int a,b;
          sc(a); sc(b);
          if(hashTable[a] == b ){
               printf("Chandu\n");
          }
          else printf("Chandni\n");
     }
}

Second solution

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <fstream>
#include <set>
#include <map>
#include <cmath>
#pragma comment(linker,"/STACK:116777216")
#define MAXN 100100

using namespace std;

int v[2000000],t;
double fi =((double)((1+sqrt(5))/2.0));

int main()
{
    for(int i=1;i<=1000000;i++)
        v[i]=-1;
    
    for(int i=1;i<=1000000;i++)
        v[(int)(fi*(double)i)] = (int)(fi*fi*i);

    scanf("%d",&t);
    while(t--){
        int a,b;
        scanf("%d %d",&a,&b);
        if(v[a]==b)
            printf("Chandu\n");
        else
            printf("Chandni\n");
     }
}