Game of Piles Version 1 Solution Codechef
There are N piles where the ith pile consists of Ai 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.
Input Format
- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains a single integer NN denoting the number of piles.
- Next line contains NN space-separated integers A1,A2,…,AN – denoting the number of stones in each pile.
Output Format
- For each test case, output CHEF if Chef wins the game, otherwise output CHEFINA.
- Note that the output is case-insensitive i.e. CHEF, Chef, cHeF, and chef are all considered the same.
Constraints
- 1≤T≤1000
- 1≤N≤105
- 1≤Ai≤109
- Sum of N over all test cases does not exceed 2⋅105.
Sample Input 1
3
2
2 2
1
10
3
1 5 6
Sample Output 1
CHEFINA
CHEFINA
CHEF
Explanation
- Test Case 1: No matter which stone Chef removes, Chefina will remove the remaining stone from the same pile and make it empty.
- Test Case 2: Since there is only 1 pile containing 10 stones, the game will last exactly 10 moves with last move made by Chefina.
- Test Case 3: Chef can remove 1 stone from the first pile and thus make it empty.
SOLUTION
Program: Game of Piles Version 1 Solution in Python
for i in range(int(input())):
n=int(input())
l=list(map(int,input().split()))
k=0
ec=0
oc=0
for i in l:
if(i==1):
print("CHEF")
k=1
break
elif(i%2==0):
ec+=1
else:
oc+=1
if(k==0):
if(oc%2==0):
print("CHEFINA")
else:
print("CHEF")
Program: Game of Piles Version 1 Solution in C++
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
for(int i=0;i<t;i++){
int n;
cin>>n;
int arr[n];
int minm = 3;
int sum = 0;
for(int k=0;k<n;k++){
cin>>arr[k];
minm = min(arr[k], minm);
sum += arr[k] - 2;
}
if(minm == 1){
cout<<"CHEF"<<endl;
continue;
}
else{
if(sum%2 == 0) cout<<"CHEFINA"<<endl;
else cout<<"CHEF"<<endl;
}
}
return 0;
}
Program: Game of Piles Version 1 Solution in Java
import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
while(t-->0){
int n=sc.nextInt();
int a[]=new int[n];
int sum=0,c=0;
for(int i=0;i<n;i++){
a[i]=sc.nextInt();
c=(a[i]==1)?++c:c;
sum+=a[i];
}
if(c>0) System.out.println("CHEF");
else{
if(sum%2==0) System.out.println("CHEFINA");
else System.out.println("CHEF");
}
}
}
}
Related: