PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Utkarsh Gupta
Tester: Satyam, Jatin Garg
Editorialist: Devendra Singh
DIFFICULTY:
1135
PREREQUISITES:
Basics of Game Theory
PROBLEM:
There are N piles where the i^{th} pile consists of A_i stones.
Chef and Chefina are playing a game taking alternate turns with Chef starting first.
In his/her turn, a player can choose any non-empty pile and remove exactly 1 stone from it.
The game ends when exactly 1 pile becomes empty. The player who made the last move wins.
Determine the winner if both players play optimally.
EXPLANATION:
The problem can be solved by dividing it into two cases:
Case 1 : There is a pile which has only 1 stone.
Chef starting first can remove a stone from that pile and win the game. Therefore the winner of the game in this case is Chef.
Case 2 : All the piles have at least 2 stones.
Removing a stone from a pile that contains exactly 2 stones is a definite losing move as the opponent can then remove the last stone from that pile and win the game. Therefore the players will keep removing stones until all piles contain exactly 2 stones. Now at this state of the piles whoever makes a move loses the game. Therefore the winner is decided by the total number of stones removed (moves made) before every pile has exactly 2 stones.
Let sum represent the total number of stones in all the N piles. If sum - 2\cdot N is even the winner is Chefina otherwise the winner is Chef.
TIME COMPLEXITY:
O(N) for each test case.
SOLUTION:
Setter's solution
//Utkarsh.25dec
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
using namespace std;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=500023;
bool vis[N];
vector <int> adj[N];
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
int sumN=0;
void solve()
{
// Version 1
int n=readInt(1,100000,'\n');
sumN+=n;
assert(sumN<=200000);
long long A[n+1]={0};
ll sum=0;
int cnt=0;
for(int i=1;i<=n;i++)
{
if(i==n)
A[i]=readInt(1,1000000000,'\n');
else
A[i]=readInt(1,1000000000,' ');
sum+=A[i];
if(A[i]==1)
cnt++;
}
if(cnt>=1)
{
cout<<"CHEF\n";
return;
}
else
{
if(sum%2==1)
cout<<"CHEF\n";
else
cout<<"CHEFINA\n";
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL),cout.tie(NULL);
int T=readInt(1,1000,'\n');
while(T--)
solve();
assert(getchar()==-1);
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}
Editorialist's Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(), _obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
ll INF = 1e18;
const int N = 1e5 + 11, mod = 1e9 + 7;
ll max(ll a, ll b) { return ((a > b) ? a : b); }
ll min(ll a, ll b) { return ((a > b) ? b : a); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void sol(void)
{
int n;
cin >> n;
vll v(n);
ll sum = 0, mi = INF;
for (int i = 0; i < n; i++)
{
cin >> v[i], sum += v[i];
mi = min(mi, v[i]);
}
if (mi == 1)
cout << "CHEF\n";
else if ((sum - 2 * n) % 2 == 0)
cout << "CHEFINA\n";
else
cout << "CHEF\n";
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int test = 1;
cin >> test;
while (test--)
sol();
}
