Page Contents
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:
- Journey of the Knight Solution Codechef
- Slow Solution Solution Codechef
- Chef and Candies Solution Codechef
- Pass the Exam Solution Codechef
- Bidding Auction Solution Codechef