OneDimensionalRobot
SRM 608 · 2013-12-22 · by rng_58
SRM 608 · 2013-12-22 · by rng_58 · Math
Problem Statement
Problem Statement
A robot is placed on an infinitely long line. Initially the position of the robot is 0. Cat Snuke sends commands to move this robot.
You are given twoString[] s commands1 and commands2. Concatenate all elements of commands1 and commands2 in the given order to get a String S. For each i, the i-th character of S (0-based index) represents the i-th command Snuke sends. If the i-th character of S is 'R', the robot moves one unit to the right (i.e., from position x to position x+1). If this character is 'L', the robot moves one unit to the left (i.e., from position x to position x-1). The robot has a built-in safety mechanism that prevents it from going too far and losing the signal. The safety mechanism makes sure that the robot always stays between the positions -A and B, inclusive. If the robot receives the command 'R' when the robot is at B, or the command 'L' when the robot is at -A, the command will be ignored.
Cat Snuke is interested in the final position of the robot when all commands are sent. You are given fourint s minA, maxA, minB, and maxB. For each pair (A, B) that satisfies minA <= A <= maxA and minB <= B <= maxB, find the final position of the robot. Return the sum of the final positions.
You are given two
Cat Snuke is interested in the final position of the robot when all commands are sent. You are given four
Constraints
- commands1 will contain between 1 and 50 elements, inclusive.
- commands2 will contain between 0 and 50 elements, inclusive.
- Each element of commands1 and commands2 will contain between 1 and 50 characters, inclusive.
- Each character in commands1 and commands2 will be either 'R' or 'L'.
- minA will be between 1 and 5000, inclusive.
- maxA will be between minA and 5000, inclusive.
- minB will be between 1 and 5000, inclusive.
- maxB will be between minB and 5000, inclusive.
Statement by TopCoder, Inc. — view the original on the archive.
Examples
0)
{"RRLRLLRRLL"}
{}
2
2
1
1
Returns: -1
The only valid (A, B) pair is (2, 1). The robot will move in the following way: 0 -> 1 -> 1 -> 0 -> 1 -> 0 -> -1 -> 0 -> 1 -> 0 -> -1.
1)
{"RLRRLRLLRRLLLRLRLLRL"}
{}
2
3
1
2
Returns: -9
When (A, B) = (2, 1), the final position is -2. When (A, B) = (2, 2), the final position is -2. When (A, B) = (3, 1), the final position is -3. When (A, B) = (3, 2), the final position is -2.
2)
{"RLRRLRRRLLLLLRLRRLLLLRRRRLLRLLRLRRRLLRRLRLLRLLRRRL", "LRLRLRLLRLLLRRLLRLRRLLLRLLRLLRLLLLRRRLLRLRRRLLRRRR"}
{}
3
5
2
4
Returns: 17
3)
{"LLRLLLLLLLLLLLLLLLRLLLLLLLLLLLLLLLLLLLLLLLLLLLLLRL", "LLLLLRLLLLLLLLLLLLRLLRLLLRLLLLLLLLLLLLLLLLLLLLLLLL", "RLLLLLLLRRLLLLLLLLLLLLLLLRLLLLLLLLLLRLLLLLLLLLLLLL", "RLLRLLLLLLLLLLLLLLLLLLRLRLLLLRLLRLLRLLLLRLLLLRLLLL", "LRLLLLLRLLLLLLLLLLLLLLLRLLLLLLLLLLLLLLLLLLLLLLLLLL", "LLRLLLLLLLLLLLLLLLLLLRLLLLLLLLLLLLLLLRLLLLLLLLLLLL", "RLLLLLLLLLLLLRLLLLLLLLLRLLLLLLRLLLLLRLLLLLLLLLLLLL", "LLLLRLLLLLLLLLLLLLLLLLLLLLRLLLLLLLLLLLLLLLLLLLLLLL", "LLLLLRLLLRLLLLLLLLLRLLLRLLLLLLLRLLLLLLLLLLLLLLLLLL", "LLLLLLLLLLLLRLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLRLLLLLL", "LLLLLLLLLLLLLLLLLLLLLLLLLLRLLRLLLLLLLLLLLLRLLLLLLL", "LLLRLLLLLRLLLLLLLLLLLLLLLLLLLLLLLRLLLLLLLRLLLLLLLL", "LLLLLLLLLLLLLLLLLLLRLLLLLLLLLLLLLLLLLLLLLLRLLLLLLL", "RLLLLLLLLRLLLLLLLLLLLLLLRLLLLLLLLLLLLRRRLLLLLLLLLL", "LLLLRLLLLLLLLLLLLLRLLLLLLLLLLLLLLLLLLLRLLLLLLLLLLL", "LLLLLLLLLLLLLLRLLLLLLLLLLLLLLLLLLLLLRLLLRLLLLLLLLL", "LLRLLLLLRLLLRLLLLLLLLLLRLLLLLLLLLLLLLLLLLLLLLLLLLL", "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLRLLLLLLRLRLRLLLLLLLR", "LLLLLLLLLLLLLLLLLLLLLLLLRLLLLLLLLLLLLLLRLLLLLLRLLL", "LLLLLLLLLLLLLLRLLLLLLLLLLLLLRRLLLLLLLLLLLLLLLLLLLL", "LLLLLLLLLLLLLLLLLLLLLLLLLLLLRLLLLLRLRLLLLLLLLLLLLL", "LLLLLLRLLLLLRLLLLLLLLLLLLLLLLLLLLLRLLLLLLLLLLLLLLL", "LLLLLLLLLLLLLLLLLLRLLLLLLRLLLLLLLLLLLLLLLLLLLLRLLL", "LLLLLRLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLRLLLL", "LLLLLLRLLLLLLLLLLLLLLRLLLLLLLLLLLLLLLLLLLLRLLLLRLL", "LLLLLLLLLLRRLLLLLLRLLRLRLLLLLLLLLLLLLLLLLLLLLLLLLL", "LLLLRLLLLLLLLLLLLLLLLLLLLLLLLLLLRLLLLLLLLLLLLLRLLL", "LLLLLLLLLLRLLLLLLLLLLLLLRLLLLLLLLRLLLLLLLLLLLLLLRL", "LLLLLLLLLLLLRLLLRLLLLLLRRLLRLLLLLRLLLLLLRLLLLLLLLL", "LLRLLLLLLLLLLLLLLLLLLLLLLLLLLLLLRLLLLLLLLLLLLLLLLL", "LLLLRLLLLLLLLLLLLLLLLLLLLLLLRRLLLLLLLLLLLLRLLLRLLL", "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", "LLLLLRLLLLLLLLLLLLLLLLLLLLRLLLRRLLLLRLLLLLLLLLLLLL", "LLLLLLLLLLLLLLLRRLLLLLLLLLLLLLLLLLRLLLLLLLLLLRLLRL", "LLLLLLLRLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLRRLL", "LLRLLLLLLLLLLLLLLLLLLLLLRLLRLLLLLLLRLLLLLLLLLLLLLL", "LLLLLLLLLLLLLLLLLLRLLLLLLLLLRLLLLLLLLLLRRLLLLLLLLL", "LLLLLLLLLLLLLLRLLLLLLLLLLLLLLLLLLLLLLLLRLLLLLLLLLL", "LLLLLLLLLLLLLLLLLLRLLLLLLLLLLRLLLLLLLLLLLLLLLLLLLL", "LLLLLLLLLLLLLLLRLLLLLLLLLRLLLLLLRLLRLLLLLLLLLLLLLL", "LRLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLRLLLLLLLRLLLLL", "LLLLLLLLLLLLLLLLLLLLLLLLLRLLLLLLLLLLLLLLLLLLLLLLLL", "RLLRLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLRLLLLLLLL", "LLLLLLLLLLLLLLLLLLLLRLLLRLLLLLLLLLLLLLLLLLLLLLLLLL", "LLLLRLRLLLLLLLLLLLLLLLLLLRLLLRRLRLLLLLLLRLLLLLLLLL", "LLLLRLLLRLLLLLLLLLLLLLLRLLLLLLLLLLLLLLLLLLLLLLLLLL", "LLRLRLLLLLRLLLLLLLLLLLLLLLLLLLLLLLLRLLLLLLLLLLLLLL", "LLLRLLLLLLLLLLLLLRLLLLLLLLLLLLLLLLLLLRLLLLLLLLLLLL", "LLLLLRLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLRLLLLLL", "LLLLLRLLLLLLLLLLLLLLLLLLLLLLRLLLLLLLLLLRLLLLLLLLLL"}
{"LLLLLLLLLLLLLLLLLRLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", "LLLLRRLRLLLLLLLLLRLRLLLLLLLLLLLLRLLLLLLLLLLLLLLRLL", "LLLLLLLLLRLLLLLLRLLLLLLLLLLLLRLLRLLLLLLLLLLLLRLLLL", "LLLLRLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLRLLLLRLLLLR", "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", "LLLLLLLLLLLLLLLLLLLLLLLLLLRLLLLLLLLLLRLLLLLLLRLLLL", "LLLLLLLLLLLLLLLLRLLLLLLLLLRLRLLLLLLRLLLLLLLRLLLLRL", "LLRLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", "RLLLRLLLLRLLLLRLLLLLLLLRLLLLLLLLLLLRLLLLRLLLRLLLLL", "LLLLLLLLLLLLLLRLLLRLLLRLLLLLLLLRRLLLLLLLLLLLLLLLLL", "LLLLLLLLLLLLLLLLLLLLLLLRLLLLLLLLLRLLLLLRLLLLRLLLLL", "RLLRLLLLLLLLLLLLRLLLLLLLLLLLLLLRLLLLLLLLLLLLLLLLLL", "LLLLLRLLLLLLLLLLLLLLLLLLLLLLLLLLRLLLLRLLLLLLLRLLLL", "LRLLLLLLLLLLLLLLLLLLLLRLLLLLLLLLLLLLLLLLLLLLLLLLLL", "LRRLLLLRLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", "LLLLLRLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLRLLLLLLLLLL", "LLLLRRLLLLLLLLLLLLLLLLRLLLLLLLLRLLLRLLLLLLLLLLLLLL", "LLLLLLLLLLLLLLLRLLLLLLRLLLLLLLLLLLLLLLLLLLLLLLLLLL", "LLLLLLLLLLLLLRLLLRLLLLLLLLLLLLLLRLLLLLLLRLLRLLRLLL", "LLLLLLRLLLLLLLLLRLLLRLLLLLLLLLLLLRLLLLLLLLLRLLLLLR", "LRLLLLLLLLLLLLLLLLLLLLLRLLLLLLLLLLLLLLLLLRLLLLLLLL", "LLLLLLLLLLRLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLR", "LLLLLLLLLLRLLLLLRLLLLLLLLLLLLLLRLLLLLLLLLLRLLLLLRL", "RLLLLLLRLLLLLLLLLLLRLLLLLRLLLLLLLLRRLLLLLLLRLLLLLL", "LLLLLLRLLLRRLLRLLLLLLLLLLLLLLLLRLLLLLLLLLRLLLLLLLR", "LLLLLLLLLLLLLLRRLRLLLLLRLLLLLLLLLLLLLLLLLLLLLLLLLL", "LLLLLLLLLRLLLLLLLLRLLLLRLLLLLLLLLLLLLLLLLLLLLLLLLL", "LLLLLLLLRLLLLLLLLLLLLLLLRLLLLLLLLLRLLLLLLLLLLLRLLL", "LRLLLLLLLLLLLLLLLLLLLLLLLLLLLLRLLLRLLLRLLLRLLLLLLL", "LLLLLRLRLLLLLLLLRLLRLLLLRLLLLLLLLLLLLLLRLLLLLLLLLL", "LLLLLLRLLLLLLLLLLLLRLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", "RLLLLLLLLLLRLLLLLLRLLLLLLLLRLLLLLLLLLLLLLRLLLLLLLL", "LLLLLLLLLLLLLLLLLLRLLLLLLLLLLLLLLLRLLLLLLLLLLLLLLL", "LLLLLRLRRLLLRLRLLLLLLLLLLLLLLRLLLLLLLLLLLLLLLLLLLL", "LRLLLLLLLLLLLLRLLRLLLLLLLLLLLLLLLLLRLLLLRLLLLLLLLL", "LLLLLRLLLLLLLLLLLLLLLRLLLLLLLLLLLLLLLLLLLLLLLLLRLL", "LLLLLLLLLLLLRLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", "LLLLLLLLLLLRLLLLLLLLLLLLRLLLLLLLLLLLLLLLLLLLLLLLLL", "LLRLLLRLLLLLLLLLLLRLLLLLLLLLRLLRLLLLLLLLLLLLLLLLLL", "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLRRLLLLLLL", "RLLLLLLLLLLLLLLLLLLLRLLLLLLLLLLLLLLLLRLRLLRRLLLLLR", "LLLLLLLLLLLRLLLLLLLLLLLLRLLLRLLLRLRLLLRLLLLLLLLRLL", "LLLLLLLLLLLLLLLLLLLLLLLRLLLLLLLLLLLLLLLLLLLLLLLLLL", "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLRRLLLLLLLLLLLLLLLLL", "LLLLLLLLLLRLRLLLLRLRLLLLLLLLLLLLLLLLLLLLLRLLLLLLLL", "LLLLLLLLLLLLRLLLLLLRLLLLLLLLRLLLLLLLLRLLLRLLLLLLLL", "LLLLLLRLLLLLLLLLLLRLLLLLLLLLLLLLLRRLLLLLLLRLLLLLLL", "LLLLLLLLLRRLRLLLLLLRLLLLLRLLLLLLLLLRLLLLLLLLLRLRLL", "LLLLLLLLRLLLLLLLLLLLLLLLLLLRLLLLLLLLLLLLLLLLLLLRLL", "LLLLLLLLLRLLLLLLLLRLLLLL"}
2210
2747
678
2141
Returns: -1952145912
4)
{"RLRRLLLLRLLLRRLRRRLRRRLLLLLRRRLRRRLLRRRRLRLRLRLLLR", "LLRRRLLRRLLLLRLRLRLLLLLRRLLLRLLRRRRLRLLRLRRLLRLRLR", "RLLLRRLLRLLLLLRRLRRRRRRRLRLLRRLLRLRRLRRLRLRLRRLRLL", "RRRRRRRRLRLRRLRRRRRLRRLLLLLRRLRLRRLLRLLLRLLRRRLLLL", "RRRRLRRLRRLLRLLLRLRRLLLLRRRLRLLLRRRLRRRRLRRRRLLLRR", "RRLRLLRLLLLRLRLLRRRLLLRRRLLRLRRLRRLLRLRRLLLLLLLRRR", "LLRRLRRLRLLRRLLRRLRRLRLRLRRLLLRRLLLRLRLLLLRRRLLRRL", "RRRRLRLLLRRRLRRLRRLLLLRRRLRLRLLLLRRLLRLLLRLRLLRLLL", "RLRLRLLLLRLLLLRLLRRLRRRRLRRRLRRLLRLLLRLRRLRRLRLRRL", "LLLLRRLLRLRRRRLLRRRRRRLLL"}
{}
192
3228
721
4244
Returns: 32107164
Submissions are judged against all 164 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class OneDimensionalRobot with a public method long long theSum(vector<string> commands1, vector<string> commands2, int minA, int maxA, int minB, int maxB) · 164 test cases · 2 s / 256 MB per case