PROBLEM STATEMENT
Fox Ciel and Toastman are playing a game.
The game uses a memory and N cards. Initially the value of the memory is set to zero. You are
given a vector cards containing exactly N elements. cards[i] is the number written on the
i-th card.
Ciel and Toastman take alternate turns, and Ciel plays first. In each turn, the player chooses a
card and removes the card from the game (this card can't be used later). If the chosen card
contains x and the value of the memory is y, the value of the memory is changed to (x | y). The
'|' symbol stands for bitwise OR (see notes for clarification). If a player can't make a move
(because there are no cards left), or if after a player's move the memory becomes 511, this player
loses.
Determine the winner when both players play optimally. If Fox Ciel wins, return "Fox Ciel" (quotes
for clarity). If Toastman wins, return "Toastman" (quotes for clarity).
DEFINITION
Class:FiveHundredEleven
Method:theWinner
Parameters:vector
Returns:string
Method signature:string theWinner(vector cards)
NOTES
-If a and b are single bits then a | b is defined as max(a, b). For two integers, A and B, in
order to calculate A | B, they need to be represented in binary: A = (an...a1)2, B = (bn...b1)2
(if the lengths of their representations are different, the shorter one is prepended with the
necessary number of leading zeroes). Then A | B = C = (cn...c1)2, where ci = ai | bi. For example,
10 | 3 = (1010)2 | (0011)2 = (1011)2 = 11.
CONSTRAINTS
-cards will contain between 1 and 50 elements, inclusive.
-Each element of cards will be between 0 and 511, inclusive.
EXAMPLES
0)
{3, 5, 7, 9, 510}
Returns: "Fox Ciel"
If Fox Ciel chooses 510 in her first turn, the value of the memory after Toastman's turn becomes
511 regardless of his choice.
1)
{0, 0, 0, 0}
Returns: "Toastman"
The value of the memory never becomes 511. After each player chooses 2 cards, there are no cards
left and Fox Ciel loses.
2)
{511}
Returns: "Toastman"
After Fox Ciel chooses the only card in her first turn, the value of the memory becomes 511 and
Fox Ciel loses.
3)
{5, 58, 192, 256}
Returns: "Fox Ciel"
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.