Jolly Jumpers..~

Problem Statement
     
NOTE: This problem statement contains superscripts that may not display properly if viewed outside of the applet.
A number which can be represented as pq, where p is a prime number and q is an integer greater than 0, is called a prime power. If q is larger than 1, we call the number a strong prime power. You are given an integer n. If n is a strong prime power, return an vector <int> containing exactly two elements. The first element is p and the second element is q. If n is not a strong prime power, return an empty vector <int>.
Definition
   
Class:
StrongPrimePower
Method:
baseAndExponent
Parameters:
string
Returns:
vector <int>
Method signature:
vector <int> baseAndExponent(string n)
(be sure your method is public)
   
 
Constraints
-
n will contain digits ('0' - '9') only.
-
n will represent an integer between 2 and 10^18, inclusive.
-
n will have no leading zeros.
Examples
0)
 
   
"27"
Returns: {3, 3 }
27 = 33. This is a strong prime power.
1)
 
   
"10"
Returns: { }
10 = 2 * 5. This is not a strong prime power.
2)
 
   
"7"
Returns: { }
A prime number is not a strong prime power.
3)
 
   
"1296"
Returns: { }
 
4)
 
   
"576460752303423488"
Returns: {2, 59 }
 
5)
 
   
"999999874000003969"
Returns: {999999937, 2 }
 
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
     
Given a string, the reversal operation r(i, j) reverses the substring of the string from the i-th character to the j-th character (0-indexed, inclusive). A reversal chain is a sequence of reversals where the range of each reversal is included in the range of the previous reversal. Formally, the sequence r(i1, j1), r(i2, j2), ..., r(im, jm) is a reversal chain if i1 <= i2 <= ... <= im, and j1 >= j2 >= ... >= jm.
You are given a string init which contains only '0' (zero) and '1' (one) characters. You want to transform this string into the string goal using a reversal chain. Return the minimum possible length of a reversal chain that transforms init into goal. Return -1 if it is impossible.
Definition
   
Class:
ReversalChain
Method:
minReversal
Parameters:
string, string
Returns:
int
Method signature:
int minReversal(string init, string goal)
(be sure your method is public)
   
 
Constraints
-
init will contain between 1 and 50 characters, inclusive.
-
init and goal will contain the same number of characters.
-
Each character of init and goal will be '0' (zero) or '1' (one).
Examples
0)
 
   
"1100"
"0110"
Returns: 1
r(0, 2) transforms "1100" into "0110".
1)
 
     
"111000"
"101010"
Returns: 2
r(1, 4) and r(2, 3) transforms "111000" into "101010".
2)
 
   
"0"
"1"
Returns: -1
It is impposible to transform "0" into "1" by a reversal chain.
3)
 
   
"10101"
"10101"
Returns: 0
You do not have to do anything.
4)
 
   
"111000111000"
"001100110011"
Returns: 4
 
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
     
A juice company is running a promotion where each juice bottle they sell contains a code that you can redeem for a prize. There are n different codes, each corresponding to a different type of prize. The codes are evenly distributed, so the probability of winning a certain type of prize is 1/n for each bottle. The codes are written underneath the bottle caps, so you can't read them until you buy the bottles. Your goal is to collect k different types of prizes. Return the expected number of bottles you must buy to achieve this goal.
Definition
   
Class:
CollectingBonuses
Method:
expectedBuy
Parameters:
string, string
Returns:
double
Method signature:
double expectedBuy(string n, string k)
(be sure your method is public)
   
 
Notes
-
The returned value must be accurate to within a relative or absolute value of 1E-9.
Constraints
-
n and k will contain digits ('0' - '9') only.
-
n and k will represent positive integers without leading zeros.
-
n will represent an integer between 1 and 10^18, inclusive.
-
k will represent an integer between 1 and the integer n represents, inclusive.
Examples
0)
 
   
"1"
"1"
Returns: 1.0
With only 1 type of prizes you just need to buy 1 bottle.
1)
 
     
"2"
"1"
Returns: 1.0
Now there are 2 types of prizes, but any one will satisfy you, so you again need only 1 bottle.
2)
 
   
"2"
"2"
Returns: 3.0
First you buy 1 bottle and collect some type of prizes. After this, you need to collect another type of prizes. Only half of bottles contains it, so in average you must buy 2 more bottles to achieve your goal.
3)
 
   
"4"
"3"
Returns: 4.333333333333333
 
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.