ChessKnight
TCCC05 Round 1 · 2005-01-10 · by Yarin
Problem Statement
The problem statement contains an image.
Consider an empty chess board (8x8 squares), with a chess knight placed on one of the squares. The possible movements of a chess knight are marked on the picture below.
If the knight moves n times, each time picking one of the eight directions uniformly at random (possibly a direction which makes the knight leave the chess board), determine the probability that it's still on the board after n jumps. Once the knight leaves the board, it can't enter it again.
Create a class ChessKnight containing the method probability which takes an
Notes
- Once the knight leaves the board, it can't enter it again.
- Your return must have an absolute or relative error less than 1e-9.
Constraints
- x will be between 1 and 8, inclusive.
- y will be between 1 and 8, inclusive.
- n will be between 1 and 100, inclusive.
1 1 2 Returns: 0.1875
When starting at a corner, only two of the initial jumps will cause the knight to stay on the board. From these new squares, six of the eight jumps will cause the knight to stay on the board. Hence the probability that the knight will stay on the board after two jumps is 1/4 * 6/8 = 0.1875.
4 4 1 Returns: 1.0
The knight can't fall off the board if only making a single jump from a square so close to the center.
2 3 10 Returns: 0.0522148497402668
4 3 50 Returns: 8.356427906809618E-7
3 7 1 Returns: 0.75
Submissions are judged against all 62 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ChessKnight with a public method double probability(int x, int y, int n) · 62 test cases · 2 s / 256 MB per case