Jolly Jumpers..~

Problem Statement
     
Given a number N and a length L, find the shortest list of at least L consecutive non-negative integers whose sum is N. If the length of that list is 100 or smaller, return the sequence as a vector <int> in ascending order. If there is no such sequence or its length is larger than 100, return { }.
Definition
   
Class:
SequenceSums
Method:
sequence
Parameters:
int, int
Returns:
vector <int>
Method signature:
vector <int> sequence(int N, int L)
(be sure your method is public)
   
 
Constraints
-
N will be between 1 and 1000000000, inclusive.
-
L will be between 2 and 100, inclusive.
Examples
0)
 
   
18
2
Returns: {5, 6, 7 }
18 can be expressed as 5 + 6 + 7 or 3 + 4 + 5 + 6. Both of these lists contain more than 2 elements, so you should return the shortest among them.
1)
 
   
18
4
Returns: {3, 4, 5, 6 }
Now the correct answer is 3 + 4 + 5 + 6 because 5 + 6 + 7 contains less than 4 elements.
2)
 
   
18
5
Returns: { }
Both possible presentations of 18 contain less than 5 elements, so there's no answer for this case.
3)
 
   
45
10
Returns: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
 
4)
 
   
1000000000
2
Returns: {199999998, 199999999, 200000000, 200000001, 200000002 }
 
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
     
M integers are randomly independently chosen from the interval lowerBound...upperBound, inclusive. Return the probability that the K-th smallest element of the generated set is equal to N. K=1 refers to the smallest element, K=2 refers to the second smallest element, and so on.
Definition
   
Class:
KthProbableElement
Method:
probability
Parameters:
int, int, int, int, int
Returns:
double
Method signature:
double probability(int M, int lowerBound, int upperBound, int N, int K)
(be sure your method is public)
     
 
Notes
-
The returned value must have an absolute or relative error less than 1e-9.
Constraints
-
M will be between 1 and 100, inclusive.
-
lowerBound will be between 1 and 1000, inclusive.
-
upperBound will be between lowerBound and 1000, inclusive.
-
N will be between lowerBound and upperBound, inclusive.
-
K will be between 1 and M, inclusive.
Examples
0)
 
   
1
1
10
3
1
Returns: 0.1
The probability that the only chosen number will be equal to 3 is 0.1.
1)
 
   
3
1
2
2
2
Returns: 0.5
There are 8 ways to choose 3 numbers from the interval 1..2:
Numbers | 2nd smallest element
 1 1 1  |  1
 1 1 2  |  1
 1 2 1  |  1
 1 2 2  |  2
 2 1 1  |  1
 2 1 2  |  2
 2 2 1  |  2
 2 2 2  |  2
Exactly 4 of the ways have the 2nd smallest element equal to 2.
2)
 
   
3
1
3
2
2
Returns: 0.48148148148148145
There are 27 ways to choose 3 numbers from the interval 1..3, 13 of them have the 2nd smallest element equal to 2.
3)
 
   
10
1
10
1
10
Returns: 1.0000000000000003E-10
Only one of 1010 ways to choose 10 numbers from the interval 1..10 has 1 as the 10th smallest element.
4)
 
   
4
61
65
62
3
Returns: 0.15200000000000002
 
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
     
The unicorn is an exotic chess piece similar to the knight. The difference is that while the knight moves two cells in one direction and one in the other direction, the unicorn moves more than two cells in one direction and more than one in the other direction.
More precisely, each unicorn move looks as follows:
pick up the unicorn;
pick one of the four basic directions, and move the unicorn more than two cells in that direction;
pick one of the two basic directions that are orthogonal to the previous one, and move the unicorn more than one cell in that direction;
put down the unicorn.
We have a chessboard that has R rows times C columns. Each cell of the chessboard contains one of the first L letters of the alphabet. To keep the input small, the content of the cells is randomly generated using the method described below.
You are given the ints R, C, and L described above, an int seed used to generate the letters in the cells, and a string word. You want to trace the string word by taking a unicorn, placing it onto a cell containing the first letter of word, making a valid move that takes it onto a cell that contains the second letter, from there making another move to the third letter, and so on. Return the number of ways in which this can be done, modulo 1,000,000,007.
The content of the cells is generated using the following pseudocode:
x = seed;
d = (65535 div L)+1;
for (int r=0; r<R; r++)
  for (int c=0; c<C; c++) {
    x = (x * 25173 + 13849) modulo 65536;
    chessboard[r][c] = character with ASCII code (65+(x div d));
  }
Definition
   
Class:
Unicorn
Method:
countWays
Parameters:
int, int, int, int, string
Returns:
int
Method signature:
int countWays(int R, int C, int L, int seed, string word)
(be sure your method is public)
   
 
Notes
-
The path of the unicorn can contain the same cell multiple times.
-
In the pseudocode, "A div B" represents the integer part of A/B. For example, 14 div 5 = 2 and 20 div 4 = 5.
-
The author's solution does not depend on any properties of the pseudorandom generator. It would solve any input of allowed size within the given limits.
Constraints
-
R will be between 1 and 300, inclusive.
-
C will be between 1 and 300, inclusive.
-
L will be between 1 and 26, inclusive.
-
seed will be between 0 and 65,535, inclusive.
-
word will contain between 1 and 50 characters, inclusive.
-
Each character in word will be an uppercase letter ('A'-'Z').
Examples
0)
 
   
3
4
2
47
"AB"
Returns: 2
When generating the input we will compute d=32768, and then generate the content of the cells. The variable x will have the following values, in order: 17332, 39133, 37242, 14235, 656, 12265, 20598, 6471, 51372, 44853, 44210, and 45363. The generated chessboard looks as follows:
ABBA
AAAA
BBBB
There are only two ways a unicorn can trace the word "AB" on this chessboard. It has to start in one of the two top corners, and then jump into the opposite corner.
1)
 
   
5
5
2
47
"CD"
Returns: 0
No letter C on this board.
2)
 
   
4
4
1
42
"AA"
Returns: 20
The unicorn can start in one of the four corner cells (and then has three possible jumps), or at one of the 8 cells that share a side with a corner cell (and then only have one possible jump). This gives us 4*3 + 8*1 = 20 ways to trace the word.
3)
 
   
4
4
1
42
"AAAAA"
Returns: 172
 
4)
 
   
1
1
5
54321
"ABCDE"
Returns: 0
The board is too small. No word longer than one character can be traced as there is no way to make a valid move.
5)
 
   
8
8
26
226
"TOPCODER"
Returns: 1
The board looks as follows:
AILFPSPF
DZIOMYCE
QOODZARU
YVOTLTRX
LSRIGANL
LCIUUSNF
IWVXKTDE
OVPPNXRD
If we number the rows and columns starting from 0, with (0,0) being the upper left corner cell, the only valid path of the unicorn is (6,5)-(2,1)-(7,3)-(1,6)-(7,0)-(2,3)-(6,7)-(4,2).
6)
 
   
20
20
2
47
"AAAAA"
Returns: 373977054
Do not forget about the modulo; the actual number of paths can be huge.
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.