Register Now
Member Count: 625,907 - April 16, 2014  [Get Time]
| Login

   Problem Statement  

 Problem Statement for ChessKnight

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 int x, an int y (the start square of the chess knight, where 1,1 is one of the corners) and an int n, the number of jumps the knight will make. The method should return a double, the probability that the knight is still on the chess board after making n random jumps.

 

Definition

    
Class:ChessKnight
Method:probability
Parameters:int, int, int
Returns:double
Method signature:double probability(int x, int y, int n)
(be sure your method is public)
    
 

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.
 

Examples

0)
    
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.
1)
    
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)
    
2
3
10
Returns: 0.0522148497402668
3)
    
4
3
50
Returns: 8.356427906809618E-7

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)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       2005 TCCC Round 1 - Division I, Level Two