All Submissions


Problem Statement

Hacky has been depressed lately given that his Cat has been defeating in every game they've been playing. But Hacky has not yet given up hope ... he has designed another new game to try and beat his Cat:
  • Hacky and the Cat alternate playing first in each game.
  • A list of random numbers (of random length) is generated using a program that Hacky wrote and the Cat verified (see note below).
  • In each turn, the player can either choose to eliminate all odd-indexed numbers or all even indexed numbers.
  • The final number is the outcome of the game. If this final value is less than the average of all the numbers in the list, the player who played first loses, else he/she/it wins.

Assuming both players play optimally, you have to determine who will win the game.

Note: Hacky's Cat knows more than a 100 programming languages, is an expert in Software Development, and has a rating so high on TopCoder that the website crashed (back in 2004) due to a long long integer overflow. It has rejected job offers from Facebook, Google & Quora, as it prefers doing far more satisfying things like sleeping, drinking milk, hunting mice, and flirting with female cats from Hostels 8 and 9.

Input/Output Specifications
  • Each line will consist of the name of the player (either "Hacky" or "Cat") who will play first, followed by the non-empty list of random numbers.
  • Corresponding to each line of the input, you need to output the name of the winner (either "Hacky" or "Cat").
  • The length of the list will be less than 10000, and each element in the list will be less than 10000 too.

Sample Input


Hacky 1 2 3 4
Cat 6 3 8 1 2 4 7 5
Hacky 9 3 1 6 4 2 8 7 3


Sample Output


Cat
Cat
Cat


Problem Setter: Kaustubh Karkare

Languages: C#,JavaScript,Pascal,Perl,PHP,Python,Ruby

Time Limit: 2 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0