In this HackerEarth Coin Game problem solution, Charlie and Alan have challenged each other to a game of logic with coins.

The game consists of N piles of coins with each pile consisting of Ai coins. The game progresses as follows: in each turn, a player selects any of the piles with an even number of coins and removes exactly half the coins out of that pile. The game ends when a player can't make a move. The last move is a winning move.

Charlie makes the first move. Assuming both players play optimally, predict who wins the game.


HackerEarth Coin Game problem solution


HackerEarth Coin Game problem solution.

#include<vector>
#include<iostream>
#include<stdio.h>
#include<bitset>
#include<algorithm>
#include<functional>
#include<numeric>
#include<utility>
#include<sstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<math.h>
#include<cstdlib>
#include<ctime>
#include<cstring>
#include<climits>
#include<sstream>
#include<string.h>
#include<set>
#include<map>
#include<utility>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<bitset>

#define lli long long
#define mp make_pair
#define pi pair<int,int>
#define pli pair<lli,lli>
#define pb push_back
#define F first
#define S second

const double EPS = 1e-7;
const lli MOD = 1000000007ll;
const double PI = 3.14159265359;
lli INF = 1e18;

template <class T>T Max2(T a,T b){return a<b?b:a;}
template <class T>T Min2(T a,T b){return a<b?a:b;}
template <class T>T Max3(T a,T b,T c){return Max2(Max2(a,b),c);}
template <class T>T Min3(T a,T b,T c){return Min2(Min2(a,b),c);}
template <class T>T Max4(T a,T b,T c,T d){return Max2(Max2(a,b),Max2(c,d));}
template <class T>T Min4(T a,T b,T c,T d){return Min2(Min2(a,b),Max2(c,d));}

using namespace std;

int main()
{

    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        int cnt = 0;
        for(int i=0;i<n;i++)
        {
            int x;
            cin>>x;
            while(x%2==0)
            {
                x/=2;
                cnt++;
            }
        }
        if(cnt%2)
            cout<<"Charlie\n";
        else
            cout<<"Alan\n";
    }
    return 0;
}


Second solution

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <functional>
#include <sstream>
#include <fstream>
#include <valarray>
#include <complex>
#include <queue>
#include <cassert>
#include <bitset>
using namespace std;

#ifdef LOCAL
  #define debug_flag 1
#else
  #define debug_flag 0
#endif

template <class T1, class T2 >
std::ostream& operator << (std::ostream& os, const pair<T1, T2> &p) 
{
  os << "[" << p.first << ", " << p.second << "]";
  return os;
}

template <class T >
std::ostream& operator << (std::ostream& os, const std::vector<T>& v) 
{
  os << "[";
  bool first = true;
  for (typename std::vector<T>::const_iterator it = v.begin(); it != v.end(); ++it)
  {
    if (!first)
      os << ", ";
    first = false;
    os << *it;
  }
  os << "]";
  return os;
}

#define dbg(args...) { if (debug_flag) { _print(_split(#args, ',').begin(), args); cerr << endl; } else { void(0);} }

vector<string> _split(const string& s, char c) {
  vector<string> v;
  stringstream ss(s);
  string x;
  while (getline(ss, x, c))
    v.emplace_back(x);
  return v;
}

void _print(vector<string>::iterator) {}
template<typename T, typename... Args>
void _print(vector<string>::iterator it, T a, Args... args) {
    string name = it -> substr((*it)[0] == ' ', it -> length());
    if (isalpha(name[0]))
      cerr << name  << " = " << a << " ";
  else
      cerr << name << " ";
  _print(++it, args...);
}

int get_cnt(int x) {
  int cnt = 0;
  while (x % 2 == 0) {
    cnt += 1;
    x /= 2;
  }
  return cnt;
}

void solve() {
  int n;
  scanf("%d", &n);
  int cnt = 0;
  for (int i = 0; i < n; i++) {
    int x;
    scanf("%d", &x);
    cnt += get_cnt(x);
  }
  printf("%s\n", cnt % 2 == 0 ? "Alan" : "Charlie");
}

int main()
{
#ifdef LOCAL
  freopen ("input.txt", "r", stdin);
#endif

  int tests;
  scanf("%d", &tests);
  for (int i = 0; i < tests; i++) {
    solve();
  }

  return 0;
}