Treasure
SRM 109 · 2002-08-14 · by brett1479
SRM 109 · 2002-08-14 · by brett1479
Problem Statement
Problem Statement
You are participating in a treasure hunt and have been given directions to the
treasure. The directions are written as a String containing the characters
'U', 'D', 'L', and 'R'. For example:
"UUURDR" means take 3 paces up, 1 pace to the right, 1 pace down, and another pace to the right.
Some trusted sources have informed you that certain parts of the directions are incorrect. This means if the directions incorrectly say 'U' at some point, it could either be 'D', 'L', or 'R'. Given the directions and the incorrect parts determine how many possible locations the treasure can be in. For example: directions = "UUR"
incorrect = {0,2}
This means that characters 0, and 2 in directions are false (directions are 0-based). Taking into account that character 0 ('U') and character 2 ('R') are incorrect, the possibly correct directions are:
"RUD","RUL","RUU","LUD","LUL","LUU","DUD","DUL","DUU"
The pictures below illustrate this data:
Create a class Treasure that contains the method numPlaces, which takes a String directions, and aint[] incorrect and returns the number of possible
locations the treasure could be at.
"UUURDR" means take 3 paces up, 1 pace to the right, 1 pace down, and another pace to the right.
Some trusted sources have informed you that certain parts of the directions are incorrect. This means if the directions incorrectly say 'U' at some point, it could either be 'D', 'L', or 'R'. Given the directions and the incorrect parts determine how many possible locations the treasure can be in. For example: directions = "UUR"
incorrect = {0,2}
This means that characters 0, and 2 in directions are false (directions are 0-based). Taking into account that character 0 ('U') and character 2 ('R') are incorrect, the possibly correct directions are:
"RUD","RUL","RUU","LUD","LUL","LUU","DUD","DUL","DUU"
The pictures below illustrate this data:
'P' marks the path taken 'X' marks possible locations with treasure 'S' marks the start point 'S' marks the start point path based on directions possible locations after correcting path ..PP. .X.X. ..P.. X.X.. ..S.. .XSX. ..... ..X.. ..... .....Even though there are 9 different paths that could be correct only 7 unique locations could have treasure so your method would return 7.
Create a class Treasure that contains the method numPlaces, which takes a String directions, and a
Constraints
- directions will have length between 1 and 10 inclusive
- directions will only contain the characters 'U','D','L', and 'R' (quotes for clarity)
- incorrect will contain between 0 and k elements inclusive, where k is the length of directions
- Each element of incorrect will be between 0 and k-1 inclusive, where k is the length of directions
- incorrect will contain no duplicate elements
Examples
0)
"UUR"
{0, 2}
Returns: 7
This is the example above.
1)
"RRRUUURRL"
{}
Returns: 1
The path is completely correct so there is only one possible treasure location.
2)
"RRRRRRRRRR"
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
Returns: 66
This example tests the speed of your code.
3)
"ULDDUR"
{3, 2}
Returns: 6
4)
"RRULDURR"
{0, 4, 5}
Returns: 13
Submissions are judged against all 30 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class Treasure with a public method int numPlaces(string directions, vector<int> incorrect) · 30 test cases · 2 s / 256 MB per case