AKVOD06 - Cartman and Butters Game
Cartman and Butters are playing a simple game. They have āNā boxes and each box has some amount of money inside it. The boxes are numbered as 1, 2 up to N. In each turn a player can remove a maximum of X(i) amount of money from box i. Initially the value of X(i) (1 <= i <= N) is āZā for all the boxes. At any point a player can select the box i and a value K (1 <= K <= X(i)) and remove K amount of money from the box i and update the value of X(i) = K. That means at any point, the amount of money removed from the box can not exceed the amount of money removed from the same box previously. Now let us suppose that both the players play optimally and Cartman takes the first turn. If at any point a player can not remove any money from any box then he loses. Can you predict who will win the game?
Input
The first line will contain "T" the no. of test cases. Then "T" test cases follow. The first line of each test case will contain two integers "N" and "Z". The next line will contain "N" integers Ai (1 <= i <= N), where Ai denotes the amount of money in ith box.
Output
For each test case, print the name of winner "Cartman" or "Butters" in a separate line (without quotes).
Constraints
Example
Input: 4 1 1 2 2 2 3 3 4 8 3 8 5 10 5 10 8 5 10 20 15 Output: Butters Butters Cartman Cartman
hide comments
lnediak:
2019-01-28 03:36:15
i tried grundy number style approach, and it is WAAAAAAAAYYYY too slow now i have to figure out the right way to do it (though, i did not cache results, so in fact it was very inefficient, and i also didn't consider that permutations of one thing are all the same...) Last edit: 2019-01-28 03:37:42 |
|
Kanish_The_Vista:
2014-05-18 20:48:38
@Ankit Kumar Vats could you expalin me the last test case |
|
Bhavik:
2014-03-16 20:16:09
nice one:) |
|
Prasun Joshi:
2014-02-25 19:45:48
please explain the test cases |
Added by: | Ankit Kumar Vats |
Date: | 2014-02-22 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | Self |