Connection Status:
Competition Arena > SequenceOfCommands

SequenceOfCommands

SRM 473 · 2009-11-12 · by misof

SRM 473 · 2009-11-12 · by misof · Brute Force, Simple Math, Simulation
Class Name: SequenceOfCommands
Return Type: String
Method Name: whatHappens
Arg Types: (vector<string>)
Problem Statement

Problem Statement

You are standing on some arbitrary point in the infinite plane.

You are given a String[] commands that contains the commands you have to execute. Each character of each element of commands is one command. The commands must be executed in the given order: first you execute all commands in the first element of commands one by one, then those in the second element, etc.

There are only three types of commands: 'S' means "step forward", 'L' means "turn 90 degrees to the left", and 'R' means "turn 90 degrees to the right". All your steps have the same length.

You will be executing the commands forever: after you execute the last character of the last element of commands, you will always start from the beginning again.

We say that your path is bounded if there is some positive real number R such that while executing the infinite sequence of steps you will never leave the circle with radius R steps and center at your starting location.

Given the String[] commands, your method should determine whether your path will be bounded or not. Return the String "bounded" (quotes for clarity) if the path is bounded and "unbounded" if it is not.

Constraints

  • commands will contain between 1 and 50 elements, inclusive.
  • Each element in commands will contain between 1 and 50 characters, inclusive.
  • Each character in each element of commands will be one of 'S', 'L', and 'R'.
Examples
0)
{"L"}
Returns: "bounded"

You are standing on the same spot forever, and in each step you take a turn 90 degrees to the left. This path is clearly bounded.

1)
{"SRSL"}
Returns: "unbounded"

Imagine that you start executing the commands facing to the north. While following this sequence you will repeatedly execute the following steps: make a step to the north, rotate right, make a step to the east, and rotate left (to face north again). Given enough time, this path will take you arbitrarily far away from the spot where you started, hence it is unbounded.

2)
{"SSSS","R"}
Returns: "bounded"

While executing this sequence of commands, you will be walking along the boundary of a small square.

3)
{"SRSL","LLSSSSSSL","SSSSSS","L"}
Returns: "unbounded"
4)
{"LR"}
Returns: "bounded"

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

Coding Area

Language: C++17 · define a public class SequenceOfCommands with a public method string whatHappens(vector<string> commands) · 125 test cases · 2 s / 256 MB per case

Submitting as anonymous