Jolly Jumpers..~

Problem Statement
     
John and Brus are studying string theory at the university. According to Brus, a string is called lucky if no two consecutive characters are equal. John is analyzing a string s, and he wants to know how many distinct lucky strings can be generated by reordering the letters in s. If s is a lucky string in its original ordering, it should also be considered in the count.
Definition
   
Class:
TheLuckyString
Method:
count
Parameters:
string
Returns:
int
Method signature:
int count(string s)
(be sure your method is public)
   
 
Constraints
-
s will contain between 1 and 10 characters, inclusive.
-
Each character of s will be a lowercase letter ('a' - 'z').
Examples
0)
 
   
"ab"
Returns: 2
Two lucky strings - "ab" and "ba".
1)
 
   
"aaab"
Returns: 0
It's impossible to construct a lucky string.
2)
 
   
"aabbbaa"
Returns: 1
"abababa" is the only lucky string that can be generated.
3)
 
   
"abcdefghij"
Returns: 3628800
 
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
     
John and Brus are studying string theory at the university. Their task is to create a list of all the palindromes that contain between 1 and n lowercase letters ('a'-'z'), inclusive. A palindrome is a string that reads the same forward and backward. Additionally, each palindrome in their list must contain no more than k distinct letters. Return the number of palindromes in the list modulo 1234567891.
Definition
   
Class:
TheLongPalindrome
Method:
count
Parameters:
int, int
Returns:
int
Method signature:
int count(int n, int k)
(be sure your method is public)
   
 
Constraints
-
n will be between 1 and 1,000,000,000, inclusive.
-
k will be between 1 and 26, inclusive.
Examples
0)
 
     
1
1
Returns: 26
All palindromes in the list are single character strings.
1)
 
   
2
10
Returns: 52
Now we have single and double character palindromes.
2)
 
   
3
2
Returns: 728
A slightly longer list.
3)
 
   
44
7
Returns: 240249781
 
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
     
John and Brus are playing a game where they alternate moves and John goes first. Initially, there is a string that contains only uppercase letters 'X', 'O' and 'L'. A move consists of replacing a single occurrence of 'X' with either 'O' or 'L'. After a player moves, if "LOL" (quotes for clarity) appears as a substring, that player immediately wins and the game ends. Otherwise, the game continues until there are no more 'X's left.
Both players use an optimal game strategy. If a player can win, he will follow the strategy that minimizes the number of moves in the game. Otherwise, if a player can make the game end without a winner, he will follow the strategy that does so (note that in this case the total number of moves in the game does not depend on the chosen strategy). Otherwise, if a player cannot win and cannot end the game in a draw, he will follow the strategy that maximizes the number of moves in the game.
You are given a String s containing the initial state of the game. If the game will end without a winner, return "Draw". If John will win the game, return "John x", and if Brus will win the game, return "Brus x", where x is the number of moves in the game, with no leading zeroes (all quotes for clarity).
Definition
   
Class:
TheStringGame
Method:
winner
Parameters:
string
Returns:
string
Method signature:
string winner(string s)
(be sure your method is public)
   
 
Constraints
-
s will contain between 1 and 16 characters, inclusive.
-
Each character of s will be 'X', 'O' or 'L'.
-
s will not contain "LOL" as a substring.
Examples
0)
 
   
"XXOXXXLXLX"
Returns: "John 1"
John can win by changing the 'X' between the two 'L's into a 'O'.
1)
 
   
"LXXLXXL"
Returns: "Brus 2"
Brus can win this game after John's first move, regardless of what John does.
2)
 
   
"LLOOLLOOLLOOLLOO"
Returns: "Draw"
No moves available.
3)
 
   
"XXXXXXXXXXXXXXXX"
Returns: "Brus 16"
 
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.