Statistics

Problem Statement for "RobotSimulation"

Problem Statement

There is an infinite field divided into 1x1 squares. A robot is standing in one of the squares.

You are going to make the robot move according to the following algorithm. Create a String S by concatenating times copies of the given String program. Then, go through all the characters of S from beginning to end. For each character, move the robot to an adjacent square in the direction indicated by the character. 'U' means up, 'D' means down, 'L' means left and 'R' means right.

After you have gone through all the characters of S, determine which squares have been visited by the robot. A square is considered visited if the robot has been in it at least once. The starting and ending squares are considered visited. Return the total number of visited squares.

Definition

Class:
RobotSimulation
Method:
cellsVisited
Parameters:
String, int
Returns:
int
Method signature:
int cellsVisited(String program, int times)
(be sure your method is public)

Constraints

  • program will contain between 1 and 10 characters, inclusive.
  • Each character in program will be one of 'U', 'D', 'L' or 'R'.
  • times will be between 1 and 200,000,000, inclusive.

Examples

  1. "RRR"

    100

    Returns: 301

    The robot will move to the right 300 times, so 301 squares will be visited.

  2. "DDU"

    100

    Returns: 102

    The robot will move according to the pattern "DDU" 100 times. Initially, we have 1 visited square. The first time the pattern "DDU" is applied, it adds 2 new squares, and each subsequent time this pattern is applied, only 1 new square is added. Therefore the total number of visited squares is 1 + 2 + 1 * 99 = 102.

  3. "URLD"

    100

    Returns: 3

    After each repetition of the pattern "URLD", the robot returns to the initial cell. So the answer here doesn't depend on times and is always equal to 3.

  4. "UUDUDDLLDR"

    1

    Returns: 7

  5. "UUDUDDLLDR"

    12345678

    Returns: 37037039

  6. "RRRRRRRRRR"

    200000000

    Returns: 2000000001

  7. "LLLLLLLLLL"

    200000000

    Returns: 2000000001

  8. "DDDDDDDDDD"

    200000000

    Returns: 2000000001

  9. "UUUUUUUUUU"

    200000000

    Returns: 2000000001

  10. "R"

    1

    Returns: 2

  11. "L"

    1

    Returns: 2

  12. "D"

    1

    Returns: 2

  13. "U"

    1

    Returns: 2

  14. "RDUD"

    56194568

    Returns: 112389137

  15. "RR"

    4526680

    Returns: 9053361

  16. "RDLDD"

    9794058

    Returns: 48970291

  17. "RR"

    67

    Returns: 135

  18. "LUD"

    119205853

    Returns: 238411707

  19. "DR"

    30586691

    Returns: 61173383

  20. "DLRDLLRR"

    2

    Returns: 11

  21. "DDDLDUDDDD"

    37533746

    Returns: 300269969

  22. "URL"

    69

    Returns: 139

  23. "UU"

    1316

    Returns: 2633

  24. "LDUUDDLRLL"

    7055835

    Returns: 35279176

  25. "DUDDLURLDL"

    8788

    Returns: 43941

  26. "LULDUULRUU"

    7230436

    Returns: 57843489

  27. "LLDDDULRUU"

    929159

    Returns: 5574955

  28. "UULDUULULU"

    191807942

    Returns: 1726271479

  29. "ULRUDUDULR"

    200000000

    Returns: 800000001

  30. "RULRURULUR"

    200000000

    Returns: 1800000001

  31. "RRRLLUULUU"

    200000000

    Returns: 1600000001

  32. "LUDRDLDRDL"

    200000000

    Returns: 1600000001

  33. "ULRDRUDDRR"

    200000000

    Returns: 1400000001

  34. "DDULUR"

    82939606

    Returns: 5

  35. "LDDRRLUUD"

    868364

    Returns: 2605096

  36. "URURLDDD"

    200000000

    Returns: 1000000002

  37. "UULUDUDRL"

    156665

    Returns: 469997

  38. "RURDRL"

    100172069

    Returns: 400688278

  39. "RRLLLDLDUL"

    1

    Returns: 8

  40. "DDRRURUU"

    40724

    Returns: 244347

  41. "RDLLDUR"

    7051517

    Returns: 21154554

  42. "UDLURDRDUR"

    2939460

    Returns: 14697302

  43. "RDDDDLU"

    5717

    Returns: 28588

  44. "RUULLRDRRL"

    92214

    Returns: 461073

  45. "RLDULDLRLL"

    91831

    Returns: 459157

  46. "DRRRRRLLUR"

    95653977

    Returns: 573923865

  47. "RULUDLLLLL"

    200000000

    Returns: 1600000002

  48. "DUDDRRDDLU"

    200000000

    Returns: 1400000002

  49. "DLLDUURLRR"

    200000000

    Returns: 7

  50. "DLLDURUUUR"

    200000000

    Returns: 1200000003

  51. "DUURRULURD"

    200000000

    Returns: 1200000003

  52. "DDURRLUUUU"

    200000000

    Returns: 1200000003

  53. "LURLUDULLD"

    200000000

    Returns: 1200000002

  54. "RDDDLULU"

    1

    Returns: 9

  55. "DUUURDRLLR"

    1163

    Returns: 4656

  56. "RDLULLRUUD"

    520675

    Returns: 2082705

  57. "RLLDDRLRLU"

    367913

    Returns: 1471655

  58. "DLLRRRDDUU"

    6

    Returns: 28

  59. "LDDRRRLUDU"

    2

    Returns: 13

  60. "RUULLDD"

    3730493

    Returns: 11191485

  61. "LRLRRDDU"

    182815060

    Returns: 548445183

  62. "RRDDLLU"

    109748950

    Returns: 329246856

  63. "LRLLUURRD"

    21

    Returns: 69

  64. "ULULDDDLRR"

    7378064

    Returns: 36890326

  65. "UDUDDDURRL"

    200000000

    Returns: 800000003

  66. "ULLDLRDRRR"

    90118397

    Returns: 450591991

  67. "LRRRRDLLDU"

    689016

    Returns: 3445085

  68. "URRLRLLDDL"

    1

    Returns: 6

  69. "ULRDLDDRDU"

    200000000

    Returns: 800000005

  70. "UUURRDDDUL"

    200000000

    Returns: 1200000005

  71. "DRRRRLLUUL"

    200000000

    Returns: 1200000004

  72. "LLRRURRDDL"

    200000000

    Returns: 1200000004

  73. "LLRURDRDDU"

    200000000

    Returns: 800000005

  74. "LLDURRRDU"

    223969

    Returns: 447944

  75. "DRRUULULLD"

    200000000

    Returns: 1000000008

  76. "DDLLUUURR"

    8008

    Returns: 24033

  77. "DDLRUUULR"

    6801

    Returns: 13608

  78. "DRLUUURLD"

    5453434

    Returns: 10906874

  79. "RRUUULLDD"

    3603602

    Returns: 10810815

  80. "UUDDRDRRLL"

    2

    Returns: 11

  81. "UULLLDDRR"

    9

    Returns: 36

  82. "RRDDLLLUU"

    18

    Returns: 63

  83. "UULLDLDDRR"

    5843

    Returns: 29224

  84. "RUUULLLDDR"

    35832

    Returns: 215000

  85. "LUUDDDRRRL"

    40

    Returns: 166

  86. "RLLLUUUDDR"

    234792

    Returns: 939174

  87. "DUURURRLLD"

    3

    Returns: 15

  88. "LRRURUUDDL"

    1

    Returns: 7

  89. "RUULLDLDDR"

    200000000

    Returns: 1000000008

  90. "UDDLDLLRRU"

    200000000

    Returns: 600000006

  91. "LDDUURURRL"

    200000000

    Returns: 600000006

  92. "LDDDRRRUUL"

    200000000

    Returns: 1200000008

  93. "LLUURURRDD"

    200000000

    Returns: 1000000009

  94. "DRULLLRRRR"

    12345

    Returns: 49383

  95. "RRRR"

    199999999

    Returns: 799999997

  96. "LULRLULDDR"

    200000000

    Returns: 1200000003

  97. "RRRRRRRRRL"

    200000000

    Returns: 1600000002

  98. "URULLDD"

    200000000

    Returns: 600000005

  99. "ULRDULLUDD"

    200000000

    Returns: 800000002

  100. "UUULLLDDRR"

    199888777

    Returns: 1199332669

  101. "RRRRRRRRRR"

    12132132

    Returns: 121321321

  102. "LLLLLLLLLL"

    1000

    Returns: 10001

  103. "DDDDDDDDDD"

    10000

    Returns: 100001

  104. "UUUUUUUUUU"

    100000000

    Returns: 1000000001

  105. "UUURRDDL"

    1

    Returns: 9

  106. "UUDDDDDDDD"

    200000000

    Returns: 1200000003

  107. "UUURRDDLD"

    183217318

    Returns: 732869279

  108. "URLDURLD"

    200000000

    Returns: 3

  109. "UUUUUUUUUD"

    300

    Returns: 2402

  110. "RRRRRRRRRR"

    10000

    Returns: 100001

  111. "UDRRRUDLL"

    1000

    Returns: 2006

  112. "RRU"

    2

    Returns: 7

  113. "DDDDDDDDDD"

    199999999

    Returns: 1999999991

  114. "UUUUUUUUUU"

    100

    Returns: 1001

  115. "UUUUUUUUU"

    40

    Returns: 361

  116. "D"

    1234

    Returns: 1235

  117. "LLLLLLLLLL"

    500

    Returns: 5001

  118. "LLLLLLLLLL"

    100000

    Returns: 1000001

  119. "RRUUULLDD"

    2

    Returns: 14

  120. "RRUUULLDD"

    1001

    Returns: 3012

  121. "LLLLLLLLLL"

    10

    Returns: 101

  122. "LLLLLLLLLL"

    9

    Returns: 91

  123. "RRRRRRRRRR"

    15

    Returns: 151

  124. "LLUURRRDD"

    200000000

    Returns: 600000009

  125. "UUUUUUUUUU"

    1000000

    Returns: 10000001

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: