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. CHEF, Chef, cHeF, and chef are all considered the same.
[Solution] Game of Piles Version 1 solution codechef
- 1≤T≤10001≤T≤1000
- 1≤N≤1051≤N≤105
- 1≤Ai≤1091≤Ai≤109
- Sum of NN over all test cases does not exceed 2⋅1052⋅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.