[Solution] Game of Piles Version 2 solution codechef

Game of Piles Version 2 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.

[Solution] Game of Piles Version 2 solution codechef

The game ends when exactly 22 piles become 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 2 solution codechef

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

Sample Input 1

2
2
5 10
3
1 1 3


[Solution] Game of Piles Version 2 solution codechef

CHEF
CHEFINA


Explanation

Test Case 11: The game will end when both piles become empty. Thus, the game will last exactly 1515 moves with last move made by Chef.

Test Case 22: It can be shown that Chefina has a winning strategy.