[Solution] Game of Piles Version 1 solution codechef

Game of Piles Version 1 solution codechef – There are NN piles where the ithith pile consists of AiAi 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 11 stone from it.

Table of Contents

[Solution] Game of Piles Version 1 solution codechef

The game ends when exactly 11 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 TT, 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,,ANA1,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. CHEFChefcHeF, and chef are all considered the same.

[Solution] Game of Piles Version 1 solution codechef

  • 1T10001≤T≤1000
  • 1N1051≤N≤105
  • 1Ai1091≤Ai≤109
  • Sum of NN over all test cases does not exceed 21052⋅105.

Sample Input 1 

3
2
2 2
1
10
3
1 5 6

Sample Output 1 

CHEFINA
CHEFINA
CHEF

[Solution] Game of Piles Version 1 solution codechef Explanation

Test Case 11: No matter which stone Chef removes, Chefina will remove the remaining stone from the same pile and make it empty.

Test Case 22: Since there is only 11 pile containing 1010 stones, the game will last exactly 1010 moves with last move made by Chefina.

Test Case 33: Chef can remove 11 stone from the first pile and thus make it empty.

For Solution

Click Here

Leave a Comment