RobotTesting

SRM 285 · 2006-01-24 · by Andrew_Lazarev

SRM 285 · 2006-01-24 · by Andrew_Lazarev · Brute Force, Math

Show categories

Class Name: RobotTesting

Return Type: double

Method Name: estimateCommands

Arg Types: (int, string)

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.

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

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.

2
"LURD"
Returns: 12501.0

If the robot starts in the bottom right corner, it will execute 50,000 commands.

4
"LDLDLDRRR"
Returns: 3.375

29
"RRULDD"
Returns: 53.236623067776456

697
"LLLLLDRRRRR"
Returns: 3806.5179340028694

Submissions are judged against all 98 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class RobotTesting with a public method double estimateCommands(int N, string program) · 98 test cases · 2 s / 256 MB per case