Problem Statement
     
There are N animals numbered 0 to N-1 in a zoo. Each animal is a rabbit or a cat. Their heights are pairwise distinct.  Fox Jiro can't distinguish between rabbits and cats, so he asked the following question to each animal: "How many animals of the same kind as you are taller than you?" Each rabbit tells the number of rabbits taller than him, and each cat tells the number of cats taller than her. The differences of heights are slight, so Fox Jiro can't tell which animals are taller than other animals. However, each animal is able to determine which animals are taller that him and which ones are shorter.  The answer given by the i-th animal is answers[i]. Given these numbers, return the number of configurations resulting in exactly those numbers, assuming everyone tells the truth. Two configurations are different if there exists an i such that the i-th animal is a rabbit in one configuration and cat in the other configuration.
Definition
    
Class:
Zoo
Method:
theCount
Parameters:
vector <int>
Returns:
long long
Method signature:
long long theCount(vector <int> answers)
(be sure your method is public)
    
 
Constraints
-
answers will contain between 1 and 40 elements, inclusive.
-
Each element of answers will be between 0 and 40, inclusive.
Examples
0)
 
    
{0, 1, 2, 3, 4}
Returns: 2
There are two possible configurations: all animals are rabbits or all animals are cats.
1)
 
    
{5, 8}
Returns: 0
There are only two animals. These animals are definitely lying.
2)
 
    
{0, 0, 0, 0, 0, 0}
Returns: 0
 
3)
 
    
{1, 0, 2, 0, 1}
Returns: 8
 
4)
 
    
{1, 0, 1}
Returns: 0
 
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)2003, TopCoder, Inc. All rights reserved.

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 <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).
Definition
    
Class:
FiveHundredEleven
Method:
theWinner
Parameters:
vector <int>
Returns:
string
Method signature:
string theWinner(vector <int> cards)
(be sure your method is public)
    
 
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)2003, TopCoder, Inc. All rights reserved.

Problem Statement
     
Cat Taro and Rabbit Hanako invented a new variation of "Game Of Life".  N cells are arranged around a circle. The cells are numbered from 0 to N-1. For each i between 0 and N-2, inclusive, the i-th cell and the (i+1)-th cell are adjacent to each other. The (N-1)-th cell and the 0-th cell are adjacent to each other. Each cell has exactly two adjacent cells. Each cell has a state: "live" or "die".  Taro and Hanako can decide the states of the cells at time 0. For time t > 0, the states are determined as follows:
Consider three cells: the i-th cell and the two cells that are adjacent to the i-th cell.
If at least two of the three cells are "live" at time t-1, the state of the i-th cell at time t will be "live".
If at least two of the three cells are "die" at time t-1, the state of the i-th cell at time t will be "die".
You are given a string init. The number of cells in the game (N) is equal to the number of characters in init. The i-th character of init represents the state they assign to the i-th cell at time 0. '1' means "live", '0' means "die", and '?' means undecided. Return the number of ways they can assign states to the undecided cells such that at least K cells will be in the "live" state at time T.
Definition
    
Class:
GameOfLifeDivOne
Method:
theCount
Parameters:
string, int, int
Returns:
long long
Method signature:
long long theCount(string init, int T, int K)
(be sure your method is public)
    
 
Constraints
-
init will contain between 3 and 50 characters, inclusive.
-
Each character in init will be '0' (zero), '1' (one) or '?'.
-
T will be between 0 and 1,000, inclusive.
-
K will be between 0 and the number of characters in init, inclusive.
Examples
0)
 
    
"0?1"
1
1
Returns: 1
There are two ways to replace '?' with '0' and '1': "001" and "011".
If the state is "001" at time 0, the state will be "000" at time 1. No cell is in the "live" state.
If the state is "011" at time 0, the state will be "111" at time 1. 3 cells are in the "live" state.
Only the second one satisfies the condition, so the answer is 1.
1)
 
    
"?????????"
0
1
Returns: 511
There are 512 ways to replace '?' cells with '0' or '1'. All of them except "000000000" satisfy the condition.
2)
 
    
"??0???????"
58
6
Returns: 151
 
3)
 
    
"?????????1"
47
3
Returns: 453
 
4)
 
    
"?????????1???0???1??1??????0??????0??0????1???????"
12
40
Returns: 31577324313
 
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)2003, TopCoder, Inc. All rights reserved.