Register Now
Member Count: 625,943 - April 16, 2014  [Get Time]
| Login

   Problem Statement  

 Problem Statement for FiveHundredEleven

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 int[] 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).


Method signature:String theWinner(int[] cards)
(be sure your method is public)


-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.


-cards will contain between 1 and 50 elements, inclusive.
-Each element of cards will be between 0 and 511, inclusive.


{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.
{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.
Returns: "Toastman"
After Fox Ciel chooses the only card in her first turn, the value of the memory becomes 511 and Fox Ciel loses.
{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.

This problem was used for:
       Single Round Match 511 Round 1 - Division I, Level Two
       Single Round Match 511 Round 1 - Division II, Level Three