TopCoder problem "BouncingDiceGame" used in Member SRM 465 (Division I Level Three)



Problem Statement

    The formerly celebrated general Archibald Waving has retired after losing the fifth army. His new peaceful lifestyle made him fond of board games. A particular one is a two player game in which each player has to take a checker across a sequence of cells on the board until reaching the final cell. There are n cells in the board and they are numbered from 1 to n. The dice in use has d faces and each number between 1 and d has the same probability of being the result of a dice throw. For fun purposes, Waving may play with insanely multi-faced dices. In each turn, a player throws a dice and then moves his piece up for as many positions as the face of the dice indicates. A player wins when he reaches the cell n.



Waving has been playing against his wife, Esther, who has added a new rule to the game called 'bouncing'. This rule comes into action when a player whose position is on the last cells of the board gets a dice value that is larger than necessary to reach the n-th cell. In that case, instead of winning the game, the player will bounce back to the previous cells.



Formally, if a is the current cell number in which the player's checker is located and b is the result of the dice throw then the following rules are used:

  • If a + b is less than n, the player moves the checker to cell (a + b).
  • If a + b is exactly n, the player moves the checker to cell n and hence wins the game.
  • If a + b is higher than n, the player moves the checker to cell (n - (a + b - n)).




Archibald has been wondering how does this rule affect the odds of winning the game at different states. You are given the number of cells n, the number of faces in the dice d, the cell on which Archibald's checker is currently located x and the cell on which Esther's checker is located y. Archibald is the next player to move. Return the probability of Archibald winning the game.
 

Definition

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

Notes

-The returned value must have an absolute or relative error less than 1e-9.
 

Constraints

-n will be between 10 and 5000, inclusive.
-d, x and y will be between 1 and n-1, inclusive.
 

Examples

0)
    
10
6
1
1
Returns: 0.5417251215862328
1)
    
10
2
1
1
Returns: 0.6090494791666666
With a two faces dice, the bouncing aspect of the game has less of an effect and thus the probability for the first player to win is larger.
2)
    
100
20
1
10
Returns: 0.49158887163174947
3)
    
10
5
9
1
Returns: 0.6943018666666667
Even though Waving is one cell away from the goal cell, the probability is still far from 100% due to the bouncing rule.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10780

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14182&pm=10780

Writer:

vexorian

Testers:

timmac , ivan_metelsky , gojira_tc , boba5551 , keshav_57

Problem categories:

Dynamic Programming, Math, Simulation