TopCoder problem "RobotTesting" used in SRM 285 (Division I Level Two)



Problem Statement

    

A robot is placed randomly on a cell in a NxN square grid. The robot has a program consisting of several commands, where each command is either 'U' (move up), 'D' (move down), 'L' (move left), or 'R' (move right). The commands are executed in order, and the program is cyclical (i.e., after the last command is executed, it will start over from the first command). The robot stops moving only if it has left the grid or if it has executed 50,000 commands.

You will be given an int N and a String program. Return the expected number of commands that will be executed before the robot stops. You can assume that all the cells in the grid are equally likely to be the starting cell.

 

Definition

    
Class:RobotTesting
Method:estimateCommands
Parameters:int, String
Returns:double
Method signature:double estimateCommands(int N, String program)
(be sure your method is public)
    
 

Notes

-Your return value must have an absolute or relative error less than 1e-9.
 

Constraints

-N will be between 1 and 1000, inclusive.
-program will contain between 1 and 50 characters, inclusive.
-Each character in program will be either 'U', 'D', 'L' or 'R'.
 

Examples

0)
    
2
"L"
Returns: 1.5
If the robot starts in the left column, it will leave the grid after the first command. Otherwise, it will leave the grid after the second command. These two scenarios are equally likely, so the answer is 1.5.
1)
    
2
"LURD"
Returns: 12501.0
If the robot starts in the bottom right corner, it will execute 50,000 commands.
2)
    
4
"LDLDLDRRR"
Returns: 3.375
3)
    
29
"RRULDD"
Returns: 53.236623067776456
4)
    
697
"LLLLLDRRRRR"
Returns: 3806.5179340028694

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8082&pm=5953

Writer:

Andrew_Lazarev

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Brute Force, Math