Jolly Jumpers..~

Problem Statement
     
The product value of a string is the product of all the digits ('0'-'9') in the string. For example, the product value of "123" is 1 * 2 * 3 = 6. A string is called colorful if it contains only digits and the product value of each of its nonempty contiguous substrings is distinct.  For example, the string "263" has six substrings: "2", "6", "3", "26", "63" and "263". The product values of these substrings are: 2, 6, 3, 2 * 6 = 12, 6 * 3 = 18 and 2 * 6 * 3 = 36, respectively. Since all six product values are distinct, "263" is colorful. On the other hand, "236" is not colorful because two of its substrings, "6" and "23", have the same product value (6 = 2 * 3).  Return the k-th (1-based) lexicographically smallest colorful string of length n. If there are less than k colorful strings of length n, return an empty string instead.
Definition
   
Class:
ColorfulStrings
Method:
getKth
Parameters:
int, int
Returns:
string
Method signature:
string getKth(int n, int k)
(be sure your method is public)
   
 
Notes
-
The lexicographically smaller of two strings is the one that has the smaller character ('0' < '1' < ... < '9') at the first position where they differ.
Constraints
-
n will be between 1 and 50, inclusive.
-
k will be between 1 and 1,000,000,000, inclusive.
Examples
0)
 
   
3
4
Returns: "238"
The first four smallest colorful strings of length 3 are "234", "235", "237" and "238".
1)
 
   
4
2000
Returns: ""
The number of colorful strings of length 4 is less than 2000.
2)
 
   
5
1
Returns: "23457"
 
3)
 
   
2
22
Returns: "52"
 
4)
 
   
6
464
Returns: "257936"
 
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
     
You are going to decorate a very large white board with square sheets of colored paper. Each sheet of paper can be of any non-zero size. You have chosen N colors, numbered 0 to N - 1, and you will use exactly one sheet of each color. You are given four vector <int>s, xa, ya, xb, and yb, each containing exactly N elements. The sheet of paper with color i must be placed so that its center is at either (xa[i], ya[i]) or (xb[i], yb[i]). All sides of the paper must be parallel to the coordinate axes, and no two sheets of paper can overlap each other (Two squares overlap if their intersection has a non-zero area).  Return the maximum possible size of the smallest of the N sheets of paper. The size of a square sheet of paper is its side length. If you cannot place all N sheets, then return 0 instead.
Definition
   
Class:
ColorfulDecoration
Method:
getMaximum
Parameters:
vector <int>, vector <int>, vector <int>, vector <int>
Returns:
int
Method signature:
int getMaximum(vector <int> xa, vector <int> ya, vector <int> xb, vector <int> yb)
(be sure your method is public)
   
 
Notes
-
It can be proved that the answer is always an integer.
Constraints
-
xa will contain between 2 and 50 elements, inclusive.
-
xa, ya, xb, and yb will contain the same number of elements.
-
Each element of xa, ya, xb, and yb will be between 0 and 1,000,000,000, inclusive.
Examples
0)
 
   
{ 10,  0,  7 }
{  0, 19,  6 }
{ 20, 10, 25 }
{ 20, 35, 25 }
Returns: 19

Problem Statement
     
You have just entered the Colorful Maze. You are given the layout of the maze in the vector <string> maze, where the j-th character of the i-th element is the cell at row i, column j. The following types of cells exist in the maze:
'#' - Wall. You cannot enter these cells.
'.' - Empty cell. You can walk freely into these cells.
'A'-'G' - Empty cell with a colored floor. Each of 'A'-'G' represents a different color. You can walk into these cells.
'$' - Entrance. This is the cell in which you start.
'!' - Exit. This is the cell you must reach to finish the maze.
 Colored floors with certain colors are dangerous, but you don't know upfront which colors are dangerous. You only know the probability of each color being dangerous. You are given a vector <int> trap, where the first element is the percent probability of color 'A' being dangerous, the second element is the percent probability of color 'B' being dangerous, and so on. When you step into a cell with a dangerous color, you get damaged by a trap. If you get damaged twice, you die.  When you're inside the maze, you can only move in the four cardinal directions. You cannot move diagonally. Return the probability that you can finish the maze without dying, assuming that you walk according to a strategy that maximizes this probability. See examples for further clarification.
Definition
    
Class:
ColorfulMaze
Method:
getProbability
Parameters:
vector <string>, vector <int>
Returns:
double
Method signature:
double getProbability(vector <string> maze, vector <int> trap)
(be sure your method is public)
    
 
Notes
-
The returned value must have an absolute or relative error less than 1e-9.
Constraints
-
maze will contain between 1 and 50 elements, inclusive.
-
Each element of maze will contain between 1 and 50 characters, inclusive.
-
Each element of maze will contain the same number of characters.
-
Each character in maze will be one of '#', '.', 'A', 'B', 'C', 'D', 'E', 'F', 'G', '$', and '!'.
-
maze will contain exactly one '$' and exactly one '!'.
-
trap will contain exactly 7 elements.
-
Each element of trap will be between 0 and 100, inclusive.
Examples
0)
 
    
{ ".$.",
  "A#B",
  "A#B",
  ".!." }
{ 50, 40, 0, 0, 0, 0, 0 }
Returns: 0.8
First, go left one cell, and then down one cell into the 'A'. One of two things might happen with equal probability:
You get damaged. This means all cells with color 'A' are dangerous, so you should go back and try going through the 'B' zone instead (which might also be dangerous).
You do not get damaged. This means all cells with color 'A' are safe, so you can continue through the 'A' zone and get to the exit.
The probability of reaching the exit is 0.5 * 0.6 (the first case) + 0.5 (the second case) = 0.8. The probability is the same if you try 'B' first.
1)
 
    
{ ".$.",
  "A#B",
  "A#C",
  ".!." }
{ 20, 70, 40, 0, 0, 0, 0 }
Returns: 0.86
If you try 'A' first:
You get damaged. You should go back and try going through the 'B' and 'C' zone.
You do not get damaged. You can continue through the 'A' zone.
The probability is 0.2 * 0.3 * 0.6 (the first case) + 0.8 (the second case) = 0.836. If you try 'B' first:
You get damaged. You can choose either going back to try 'A' or going ahead to try 'C'. Going through the 'A' zone is safer.
You do not get damaged. Whether 'C' is dangerous or not, you can go through 'C' and get to the exit.
The probability is 0.7 * 0.8 (the first case) + 0.3 (the second case) = 0.86. You see that trying 'B' first is a better choice.
2)
 
    
{ "$A#",
  ".#.",
  "#B!" }
{ 10, 10, 10, 10, 10, 10, 10 }
Returns: 0.0
No matter how you walk, you cannot reach the exit, so you should return 0.
3)
 
    
{ "$A..",
  "##.A",
  "..B!" }
{ 50, 50, 0, 0, 0, 0, 0 }
Returns: 0.75
 
4)
 
    
{ "$C..",
  "##.A",
  "..B!" }
{ 50, 50, 100, 0, 0, 0, 0 }
Returns: 0.5
 
5)
 
    
{ ".$.D.E.F.G.!." }
{ 10, 20, 30, 40, 50, 60, 70 }
Returns: 0.23400000000000004
 
6)
 
    
{ "CC...AA",
  "C##.##A",
  "!.E.E.$",
  "D##.##B",
  "DD...BB" }
{ 90, 90, 25, 50, 75, 0, 0 }
Returns: 0.8125
 
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.