RobotCollision

SRM 273 · 2005-11-21 · by supernova

SRM 273 · 2005-11-21 · by supernova · Simple Math, Simple Search, Iteration, Simulation

Show categories

Class Name: RobotCollision

Return Type: double

Method Name: probability

Arg Types: (int, int, string, string)

Problem Statement

You work in the field of Robotics and you are doing some black-box testing. Two robots, Robbie and Speedy, are randomly placed in a rectangular room, which is divided into xSize * ySize cells. Each robot receives a few movement commands that are executed one by one, at the same time, by both the robots.

A move is represented by an uppercase letter, which is one of the following:
- 'U': the robot moves from the coordinates (x, y) to the coordinates (x - 1, y). This command is ignored when x = 0.
- 'D': the robot moves from the coordinates (x, y) to the coordinates (x + 1, y). This command is ignored when x = xSize - 1.
- 'L': the robot moves from the coordinates (x, y) to the coordinates (x, y - 1). This command is ignored when y = 0.
- 'R': the robot moves from the coordinates (x, y) to the coordinates (x, y + 1). This command is ignored when y = ySize - 1.

Two robots may collide if they start one of their turns from the same cell, end one of their turns in the same cell, or exchange positions at one of their turns. You will be given an int xSize and an int ySize denoting the dimensions of the rectangular room, a String commandsRobbie denoting the movement commands given to Robbie and a String commandsSpeedy denoting the movement commands given to Speedy. Your task is to return the probability that the two robots will collide, taking into acount every possible start position for both of the robots. The probability for each robot to start in any specific cell is the same for all cells.

Notes

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

Constraints

xSize will be between 1 and 100, inclusive.
ySize will be between 1 and 100, inclusive.
commandsRobbie and commandsSpeedy will each contain between 0 and 10 characters, inclusive.
Each character in commandsRobbie and commandsSpeedy is either 'U', 'D', 'L' or 'R'.
commandsRobbie and commandsSpeedy have the same length.

Examples

1
10
"L"
"R"
Returns: 0.27

In this example, Robbie goes one step left and Speedy goes one step right. Out of the 100 possible starting positions (10 for each robot), 27 of them will lead to collision. A collision happens in one of the following three ways: - Robbie and Speedy start at the same cell. In this case we have an instant collision. There are 10 such starting positions. - Robbie starts at Speedy's immediate right. In this case we have a frontal collision as the two robots approach each other. There are 9 such starting positions. - Robbie starts two steps to the right from Speedy. In this case the robots end up in the same cell after they make their moves, so again, we have a collision. There are 8 such starting positions.

2
2
"DRUL"
"DRUL"
Returns: 1.0

2
2
"DRUL"
"RULD"
Returns: 0.4375

10
10
"D"
"D"
Returns: 0.012

20
50
""
""
Returns: 0.0010

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

Coding Area

Language: C++17 · define a public class RobotCollision with a public method double probability(int xSize, int ySize, string commandsRobbie, string commandsSpeedy) · 108 test cases · 2 s / 256 MB per case