Jolly Jumpers..~

Problem Statement
     
Taro and Hanako like potatoes very much. Today they decided to play Potato Game.  Initially there is a box containing n potatoes. Taro and Hanako alternate turns, and Taro goes first. In each turn, the player must eat some potatoes from the box. The number of eaten potatoes must be a power of four, i.e., 1, 4, 16, 64 and so on. The first player who cannot eat a valid number of potatoes loses. Return the name of the winner assuming that they both play optimally.
Definition
    
Class:
PotatoGame
Method:
theWinner
Parameters:
int
Returns:
string
Method signature:
string theWinner(int n)
(be sure your method is public)
    
 
Constraints
-
n will be between 1 and 1,000,000,000 (10^9), inclusive.
Examples
0)
 
    
1
Returns: "Taro"
Taro will win if he eats 1 potato in the first turn.
1)
 
    
2
Returns: "Hanako"
Taro must eat exactly 1 potato in the first turn. In the second turn, Hanako will eat 1 potato and she will win.
2)
 
    
3
Returns: "Taro"
 
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
     
There are N cards which are initially blank. First, Taro writes a distinct number between 1 and N, inclusive, on the front side of each card. The number he writes on the i-th card is taro[i]. Then, Hanako turns over all the cards and writes a distinct number between 1 and N, inclusive, on the back side of each card. The number she writes on the i-th card is hanako[i].  Now you must determine the number of distinct ways that the N cards can be arranged in a row. The cards can be placed in any order and each card can be oriented so that either its front side or back side is displayed. Two arrangements are considered distinct if the i-th card in the row shows a different number in one arrangement than it does it in the other. Return the number of distinct possible arrangements, modulo 1,000,000,007.
Definition
    
Class:
TwoSidedCards
Method:
theCount
Parameters:
vector <int>, vector <int>
Returns:
int
Method signature:
int theCount(vector <int> taro, vector <int> hanako)
(be sure your method is public)
    
 
Constraints
-
N will be between 1 and 50, inclusive, where N is the number of elements in taro.
-
Each element of taro will be between 1 and N, inclusive.
-
taro will contain no duplicate elements.
-
hanako will contain exactly N elements.
-
Each element of hanako will be between 1 and N, inclusive.
-
hanako will contain no duplicate elements.
Examples
0)
 
    
{1, 2, 3}
{1, 3, 2}
Returns: 12
If the front side of each card is displayed, the cards will be (1,2,3), and you can get (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1) by changing the order. If the back side of the second card is displayed, the cards will be (1,3,3), and you can get (1,3,3), (3,1,3), (3,3,1) by changing the order. If the back side of the third card is displayed, the cards will be (1,2,2), and you can get (1,2,2), (2,1,2), (2,2,1) by changing the order. If the back sides of both the second and third cards are displayed, the cards will be (1,3,2), and you can get (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1) by changing the order.  In total, there are 12 possibilities: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1), (1,3,3), (3,1,3), (3,3,1), (1,2,2), (2,1,2), (2,2,1).
1)
 
    
{1, 2, 3}
{1, 2, 3}
Returns: 6
You can make 123, 132, 213, 231, 312, 321.
2)
 
    
{1, 2}
{2, 1}
Returns: 4
You can make 11, 12, 21, 22.
3)
 
    
{5, 8, 1, 2, 3, 4, 6, 7}
{1, 2, 3, 4, 5, 6, 7, 8}
Returns: 2177280
 
4)
 
    
{41, 22, 17, 36, 26, 15, 10, 23, 33, 48, 49, 9, 34, 6, 21, 2, 46, 16, 25, 3, 24, 13, 40, 37, 35,
50, 44, 42, 31, 12, 29, 7, 43, 18, 30, 19, 45, 32, 39, 14, 8, 27, 1, 5, 38, 11, 4, 20, 47, 28}
{19, 6, 23, 35, 17, 7, 50, 2, 33, 36, 12, 31, 46, 21, 30, 13, 47, 22, 44, 4, 25, 24, 3, 15, 20,
48, 10, 28, 26, 18, 5, 45, 49, 16, 40, 42, 43, 14, 1, 37, 29, 8, 41, 38, 9, 11, 34, 32, 39, 27}
Returns: 529165844
 
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
     
Taro likes colorful things, especially colorful tiles.  Taro's room is an H x W rectangle divided into 1 x 1 tiles. Each tile is one of the following four colors: red, green, blue or yellow. You are given a vector <string> room. If the j-th character of the i-th element is 'R', 'G', 'B' or 'Y', the color of the tile in the j-th column of the i-th row is red, green, blue or yellow, respectively.  He decided to change the color of some tiles so that no two adjacent tiles have the same color. Two tiles are adjacent if they share a side or a corner (so a tile has at most 8 adjacent tiles). He is allowed to change at most K tiles.  Return the number of ways to change tiles that satisfies the above conditions, modulo 1,000,000,007. Two ways are considered to be different if there is at least one tile of distinct color.
Definition
    
Class:
ColorfulTiles
Method:
theCount
Parameters:
vector <string>, int
Returns:
int
Method signature:
int theCount(vector <string> room, int K)
(be sure your method is public)
    
 
Constraints
-
room will contain between 1 and 50 elements, inclusive.
-
Each element of room will contain the same number of characters.
-
Each element of room will contain between 1 and 50 characters, inclusive.
-
Each character in room will be 'R', 'G', 'B' or 'Y'.
-
K will be between 0 and the number of characters in room, inclusive.
Examples
0)
 
    
{"RG"}
1
Returns: 5
If he doesn't change any tiles, he can make "RG". If he changes the first tile, he can make "BG" or "YG". If he changes the second tile, he can make "RB" or "RY".
1)
 
    
{"BY"}
2
Returns: 12
All pairs of different colors are possible.
2)
 
    
{"RG",
 "GR"}
2
Returns: 8
The eight ways are: 
RG  RG  BY  YB  BG  YG  RB  RY
BY  YB  GR  GR  YR  BR  GY  GB
3)
 
     
{"BRYBGYRB"
,"GRYGYBBG"
,"RGBGYBYG"
,"YRBRGBYG"
,"RBGRBRGG"
,"RBGYRYBY"}
34
Returns: 489
 
4)
 
    
{"BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB"
,"BBBBBBYYYBBBBBBBBBBBBBBBBBBBBBBBBBYYYYYBBBBBBBBBBB"
,"BBBBBBYYYBBBBBBBBBBBBBBBBBBBBBBYYYYYYYYYYYBBBBBBBB"
,"BBBBBBYYYYYYYYYYYYYYYYBBBBBBBBYYYYBBBBBYYYYBBBBBBB"
,"BBBBBBYYYYYYYYYYYYYYYYBBBBBBBYYYBBBBBBBBBYYYBBBBBB"
,"BBBBBBYYYBBBBBBBBBBBBBBBBBBBBYYYBBBBBBBBBYYYBBBBBB"
,"BBBBBBYYYBBBBBBBBBBBBBBBBBBBBYYYBBBBBBBBBYYYBBBBBB"
,"BBBBBBYYYBBBBBBBBBBBBBBBBBBBBYYYBBBBBBBBBYYYBBBBBB"
,"BBBBBBYYYBBBBBBBBBBBBBBBBBBBBYYYBBBBBBBBBYYYBBBBBB"
,"BBBBBBYYYBBBBBBBBBBBBBBBBBBBBBYYYYBBBBBYYYYBBBBBBB"
,"BBBBBBYYYBBBBBBBBBBBBBBBBBBBBBBBYYYYYYYYYBBBBBBBBB"
,"BBBBBBYYYYYYYYYYYYBBBBBBBBBBBBBBYYYYYYYYYBBBBBBBBB"
,"BBBBBBYYYYYYYYYYYYYYBBBBBBBBBBYYYYBBBBBYYYYBBBBBBB"
,"BBBBBBBBBBBBBBBBYYYYYBBBBBBBBYYYBBBBBBBBBYYYBBBBBB"
,"BBBBBBBBBBBBBBBBBBYYYBBBBBBBBYYYBBBBBBBBBYYYBBBBBB"
,"BBBBBBBBBBBBBBBBBBYYYBBBBBBBBYYYBBBBBBBBBYYYBBBBBB"
,"BBBBBBYYYBBBBBBBBBYYYBBBBBBBBYYYBBBBBBBBBYYYBBBBBB"
,"BBBBBBYYYBBBBBBBBBYYYBBBBBBBBYYYBBBBBBBBBYYYBBBBBB"
,"BBBBBBBYYYYBBBBBYYYYBBBBBBBBBBYYYYBBBBBYYYYBBBBBBB"
,"BBBBBBBBYYYYYYYYYYYBBBBBBBBBBBBYYYYYYYYYYYBBBBBBBB"
,"BBBBBBBBBBBYYYYYBBBBBBBBBBBBBBBBBBYYYYYBBBBBBBBBBB"
,"BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB"}
825
Returns: 404506540
 
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.