Statistics

Problem Statement for "FrabonacciTree"

Problem Statement

The 0-th and 1-st Frabonacci trees are each single nodes. For all i > 1, the i-th Frabonacci tree is constructed as follows:

  • Create a new node r. This will be the root node of the i-th Frabonacci tree.
  • Construct the (i-1)-th and (i-2)-th Frabonacci trees.
  • Attach the (i-2)-th Frabonacci tree as the left subtree of r.
  • Attach the (i-1)-th Frabonacci tree as the right subtree of r.
The number of vertices in Frabonacci trees grows very quickly, for example there are about 4*10^10 vertices in the 50-th Frabonacci tree.

To traverse a Frabonacci tree in preorder, perform the following operations:

  • Visit the root.
  • Traverse the left subtree.
  • Traverse the right subtree.
Let's traverse a Frabonacci tree and enumerate all vertices in the order of their visiting. There is the 3-rd Frabonacci tree with enumerated vertices on the picture.

You are given three ints n, startIndex, finishIndex. Return the shortest route between the vertices startIndex and finishIndex in form of a String in the n-th Frabonacci tree. Each character of the result will be "L", "R" or "U", where "L" means a move to the left son, "R" means the move to the right son, and "U" means the move to the parent.

Definition

Class:
FrabonacciTree
Method:
shortestPath
Parameters:
int, int, int
Returns:
String
Method signature:
String shortestPath(int n, int startIndex, int finishIndex)
(be sure your method is public)

Constraints

  • n will be between 0 and 50, inclusive.
  • startIndex will be between 1 and 1000000000, inclusive.
  • finishIndex will be between 1 and 1000000000, inclusive.
  • startIndex, finishIndex less or equal than the number of vertices in the n-th Frabonacci tree.

Examples

  1. 3

    2

    4

    Returns: "URL"

  2. 3

    4

    2

    Returns: "UUL"

  3. 3

    5

    4

    Returns: "UL"

  4. 12

    10

    10

    Returns: ""

  5. 3

    1

    2

    Returns: "L"

  6. 0

    1

    1

    Returns: ""

  7. 1

    1

    1

    Returns: ""

  8. 2

    3

    2

    Returns: "UL"

  9. 3

    1

    4

    Returns: "RL"

  10. 4

    5

    7

    Returns: "R"

  11. 5

    13

    13

    Returns: ""

  12. 6

    7

    25

    Returns: "UUURRRRR"

  13. 7

    36

    6

    Returns: "UUUUULLRL"

  14. 8

    42

    15

    Returns: "UUUUUULRLR"

  15. 9

    78

    37

    Returns: "UUUUUULRRRLR"

  16. 10

    85

    20

    Returns: "UUUUUUULLRRL"

  17. 11

    6

    149

    Returns: "UUUUURLRLRR"

  18. 12

    415

    131

    Returns: "UUUUUUUUULRRLRRLL"

  19. 13

    271

    583

    Returns: "UUUUUUUUURRRLLLLR"

  20. 14

    1145

    166

    Returns: "UUUUUUUUUULLRRRRRL"

  21. 15

    1072

    1969

    Returns: "UUUUUURRRRRRRRRRR"

  22. 16

    2212

    2420

    Returns: "UUUUUUURRRRRLLR"

  23. 17

    4486

    3392

    Returns: "UUUUUUULLRRLR"

  24. 18

    4069

    4726

    Returns: "UUUUUUUURRLLLRRLR"

  25. 19

    9716

    703

    Returns: "UUUUUUUUUUUUULLLRRRRRLRLL"

  26. 20

    2970

    3862

    Returns: "UUUUUUUUUUUURLLRRRRLRLLL"

  27. 21

    30186

    28933

    Returns: "UUUUUUUUUUUUULRRRRLLLRL"

  28. 22

    12070

    30094

    Returns: "UUUUUUUUUUURLRLRRRRRRLLRLR"

  29. 23

    40705

    6489

    Returns: "UUUUUUUUUUUUUUUULLRLRLLLRRRR"

  30. 24

    68881

    79588

    Returns: "UUUUUUUUUUUURRLLLRLRLRLLL"

  31. 25

    66853

    227686

    Returns: "UUUUUUUUUUUUUUUUUURRRRRLRRRLRLRRLL"

  32. 26

    160965

    30081

    Returns: "UUUUUUUUUUUUUUUUUULLRLRLRRRRRR"

  33. 27

    347766

    516447

    Returns: "UUUUUUUUUUUUUUUUUUURRLRLRRLLRRRLRLRRR"

  34. 28

    587632

    685084

    Returns: "UUUUUUUUUUUUUUUUURLLRRRRLLRLLLRRRR"

  35. 29

    905022

    1419248

    Returns: "UUUUUUUUUUUUUUUUUURRLRRRRRRRRLRRRRRLRRRLL"

  36. 30

    1210100

    1092306

    Returns: "UUUUUUUUUUUUUULRRLRLRLLRLRL"

  37. 31

    1762581

    242142

    Returns: "UUUUUUUUUUUUUUUUUULLLRRRRRRRRRRRRLLRRRRRR"

  38. 32

    6626611

    6563843

    Returns: "UUUUUUUUUUUUUULLLLLLRRRRLLRL"

  39. 33

    7819067

    2091282

    Returns: "UUUUUUUUUUUUUUUUUUUUUUULRLRLLLRRRRRRRLLRRRRLLR"

  40. 34

    12011533

    9039321

    Returns: "UUUUUUUUUUUUUUUUUUUULRLLRRRLRRLRRRLLRRRL"

  41. 35

    29083064

    29193053

    Returns: "UUUUUUUUUUUUUUUUURRRLLRRLLRRLLRRRL"

  42. 36

    19738123

    28336247

    Returns: "UUUUUUUUUUUUUUUUUUURRRRLLRLRRRLRLRRRRRLLRR"

  43. 37

    11298334

    23427549

    Returns: "UUUUUUUUUUUUUUUUUUUUUUUUUURRRLLRLRRRRRLLRRLRRL"

  44. 38

    40258630

    96794528

    Returns: "UUUUUUUUUUUUUUUUUUUUUUUUUUUUURRRLLLLLRRLLRRRRRRRLRRRL"

  45. 39

    104115999

    183801571

    Returns: "UUUUUUUUUUUUUUUUUUUUUUUUUURRRLRRRLLRRLRRLLRRRLLRRLLR"

  46. 40

    287805697

    141495567

    Returns: "UUUUUUUUUUUUUUUUUUUUUUUUUUUULLRLRLRLRRLRLLRRRRRRLRRRLRRR"

  47. 41

    417124961

    399206745

    Returns: "UUUUUUUUUUUUUUUUUUUUUUUULRRRRLLRRRLLLLRLRRLRRRLR"

  48. 42

    305591229

    104504596

    Returns: "UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUULRRRLRRLRLRLRLLLRRRRRRLRRLRRR"

  49. 43

    83914811

    197932891

    Returns: "UUUUUUUUUUUUUUUUUUUUUUUUUURRRRRRLLLRRRLRLLLLLRLRR"

  50. 44

    123908986

    790106328

    Returns: "UUUUUUUUUUUUUUUUUUUUUUUUUUUUURRRRRLLLLRRRLLRLLLLRRRR"

  51. 45

    267227790

    108450868

    Returns: "UUUUUUUUUUUUUUUUUUUUUUUUUUUUULRLRRLLLRLLLRLRRRRLRRLLRLRR"

  52. 46

    829575040

    626625241

    Returns: "UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUULRRLRRLRLLRRRLLLLRLRLLRR"

  53. 47

    174866391

    898054880

    Returns: "UUUUUUUUUUUUUUUUUUUUUUUUUUUURRLLRLLLRLLRRLRRLRRRRRRLLLRL"

  54. 48

    304637427

    146469600

    Returns: "UUUUUUUUUUUUUUUUUUUUUUUUUUULLRRLLRRRRRLLRLLLRLLLL"

  55. 49

    752781034

    481322118

    Returns: "UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUULRRRRLRRRLLRRRLRRRLLRLRRLRRRRRL"

  56. 50

    592976931

    597963053

    Returns: "UUUUUUUUUUUUUUUUUUUUUUUUURLLRRRRLRRLRRRRRLRRRRLRRRRRR"

  57. 0

    1

    1

    Returns: ""

  58. 1

    1

    1

    Returns: ""

  59. 2

    1

    1

    Returns: ""

  60. 3

    2

    2

    Returns: ""

  61. 4

    1

    9

    Returns: "RRR"

  62. 5

    11

    12

    Returns: "L"

  63. 6

    2

    6

    Returns: "R"

  64. 7

    19

    21

    Returns: "R"

  65. 8

    53

    63

    Returns: "RR"

  66. 9

    69

    1

    Returns: "UU"

  67. 10

    77

    2

    Returns: "UUUUL"

  68. 11

    283

    283

    Returns: ""

  69. 12

    357

    427

    Returns: "RRLL"

  70. 13

    289

    1

    Returns: "U"

  71. 14

    7

    292

    Returns: "UUUUURRLL"

  72. 15

    2

    2

    Returns: ""

  73. 16

    2

    1401

    Returns: "URLLRR"

  74. 17

    1

    1

    Returns: ""

  75. 18

    183

    186

    Returns: "LLL"

  76. 19

    2911

    2912

    Returns: "L"

  77. 20

    21318

    15106

    Returns: "UUUUUUUULRLRLLRRRRRL"

  78. 21

    7

    1096

    Returns: "UUURLRRLRRLRL"

  79. 22

    3

    3

    Returns: ""

  80. 23

    63139

    1

    Returns: "UUUUUUUUUUUUU"

  81. 24

    43787

    1

    Returns: "UUUUU"

  82. 25

    106276

    106560

    Returns: "UUUURR"

  83. 26

    237620

    200981

    Returns: "UUUUULRRLRRL"

  84. 27

    6

    3200

    Returns: "RR"

  85. 28

    5

    529359

    Returns: "UUUURLRLRRR"

  86. 29

    1

    477

    Returns: "LLLLLLLLRRLL"

  87. 30

    1028471

    1028467

    Returns: "UUUU"

  88. 31

    1490744

    3

    Returns: "UUUUUUUUUUUUUUUUUUUUUUUUL"

  89. 32

    2503876

    2149655

    Returns: "UUUUUUUUULR"

  90. 33

    7222

    5176

    Returns: "UUUUUUU"

  91. 34

    15489087

    15762393

    Returns: "UUUUUUUUUUUUUUUUUUUR"

  92. 35

    12

    626225

    Returns: "UUUUUUURRRRRRRRLRRRLR"

  93. 36

    41861696

    18454931

    Returns: "UUUUUUUUUUUUUUUUUUU"

  94. 37

    14248368

    18061319

    Returns: "UUUUURRRRLRRRRRRRRRRRLRRRRRR"

  95. 38

    2692542

    17660902

    Returns: "UURRRRRRLRLRRRRRL"

  96. 39

    202611398

    137897748

    Returns: "UUUUUUUUUUUULR"

  97. 40

    199283237

    331010233

    Returns: "UUUUUUUUURRRRRRRRRRRRRRR"

  98. 41

    209090729

    215346089

    Returns: "UUUUUUUUUUUUUUUUURLRRRLRRRLLLLLRLLRRRRR"

  99. 42

    14098317

    1

    Returns: "UUUUUUU"

  100. 43

    517373664

    535828526

    Returns: "RRRRRRRRRRRRRRRRRRRRRRRRRR"

  101. 44

    517358014

    845081582

    Returns: "UUUUUUUUUUUUUUUUUUUUUUUUUUUUUURRRRRRLRRLRLRRLRLLRRR"

  102. 45

    746520919

    774844655

    Returns: "UUUUUUUUUUUUUUUUURRLRRLLLRRRRLLRRLRR"

  103. 46

    866988876

    614004934

    Returns: "ULRRLRR"

  104. 47

    668594586

    1

    Returns: "UUUUUUUUUUUUUUUUUUUUUUUUUUUU"

  105. 48

    945686688

    945690199

    Returns: "UUUURLRLLLRLL"

  106. 49

    3

    1

    Returns: "UU"

  107. 50

    2

    3

    Returns: "L"

  108. 50

    1

    1

    Returns: ""

  109. 50

    2

    1

    Returns: "U"

  110. 50

    14

    1

    Returns: "UUUUUUUUUUUUU"

  111. 50

    457652262

    848533949

    Returns: "UUUUURRRRRRR"

  112. 50

    103766324

    134662333

    Returns: "UUUUUUUUUUUUUUUUUUUUUUUURLLLRRLRRLR"

  113. 50

    7

    3

    Returns: "UUUU"

  114. 50

    11

    126486811

    Returns: "UUUURRRRRRRRRRRRRRRRRRRRR"

  115. 50

    22811882

    8

    Returns: "UUUUUUUUUUUUUUUUU"

  116. 50

    7

    5

    Returns: "UU"

  117. 0

    1

    1

    Returns: ""

  118. 1

    1

    1

    Returns: ""

  119. 2

    3

    2

    Returns: "UL"

  120. 3

    3

    2

    Returns: "UL"

  121. 4

    7

    7

    Returns: ""

  122. 5

    15

    3

    Returns: "UUUULL"

  123. 6

    9

    23

    Returns: "UUUURRRR"

  124. 7

    41

    33

    Returns: "UUU"

  125. 8

    50

    4

    Returns: "UUUUULLL"

  126. 9

    109

    95

    Returns: "UUUU"

  127. 10

    177

    122

    Returns: "UUUUUUULR"

  128. 11

    287

    287

    Returns: ""

  129. 12

    441

    463

    Returns: "RRRR"

  130. 13

    749

    745

    Returns: "U"

  131. 14

    1111

    1111

    Returns: ""

  132. 15

    1969

    8

    Returns: "UUUUUUUUUUUULLLLLLL"

  133. 16

    8

    3169

    Returns: "UUUUUUURRRRRRRRRR"

  134. 17

    5165

    5163

    Returns: "U"

  135. 18

    5

    10

    Returns: "LLLLL"

  136. 19

    12777

    13521

    Returns: "RRRRRRRRR"

  137. 20

    16725

    7

    Returns: "UUULLLLLL"

  138. 21

    35421

    35135

    Returns: "UUUUUUUUUU"

  139. 22

    57305

    57299

    Returns: "U"

  140. 23

    91983

    81273

    Returns: "UUUUUULRLLLRLRLLL"

  141. 24

    7

    11

    Returns: "LLLL"

  142. 25

    234425

    188587

    Returns: "UUUULLLRRRRRRRLRR"

  143. 26

    357415

    13

    Returns: "UUUUULLLLLLLLLLLL"

  144. 27

    635513

    622093

    Returns: "UUUUUUUUUU"

  145. 28

    392840

    12

    Returns: "UUUULLLLLLLLLLL"

  146. 29

    7

    11

    Returns: "LLLL"

  147. 30

    16

    14

    Returns: "UU"

  148. 31

    16

    4356603

    Returns: "UUUUUUUUUUUUUUURRRRRRRRRRRRRRRRRRRRRRRRRR"

  149. 32

    7049147

    7045963

    Returns: "UUUUUUUUUUUU"

  150. 33

    11405665

    15

    Returns: "UUUUUUUUUUUUUUUUUUUUUUUULLLLLLLLLLLLLL"

  151. 34

    14

    17

    Returns: "LLL"

  152. 35

    23851216

    14

    Returns: "UUUUUUUUUUUUUUUUUUUULLLLLLLLLLLLL"

  153. 36

    48315457

    15050

    Returns: "UUUUUUUUUUUUUUUUUUUUUUUUUULLLLLLLLRRLRLRL"

  154. 37

    78176229

    33297113

    Returns: "UUUUUUUUUUUUUUUUUUUUUUUUUUULLRLRLLRRLRRLRRL"

  155. 38

    126491863

    44781065

    Returns: "UUUUUUUUUUUUUUUUUUUUUUUUUUUUULRRRRRLRLRLRLLLLRRRLLLRRL"

  156. 39

    121028461

    204668301

    Returns: "UUUUUUUUUUUUUUUUUUUUUUUUURRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR"

  157. 40

    16

    126491974

    Returns: "UUUUUUUUUUUUUUURL"

  158. 41

    535823425

    18

    Returns: "UUUUUUUUUUUUUUUUUUUUUUUULLLLLLLLLLLLLLLLL"

  159. 42

    865324795

    10

    Returns: "UUUUUUUUUUUUULLLLLLLLL"

  160. 43

    7

    976843289

    Returns: "UUUUUURRLRLRRLLRRLRLLLLRRLLLLRRRLR"

  161. 44

    12

    17

    Returns: "LLLLL"

  162. 45

    22

    788994359

    Returns: "UUUUUUUUUUUUUUUUUUUURLRRRLLLLLLRRLRRRRLRRR"

  163. 46

    946829305

    20

    Returns: "UUUUUUUUUUUUUUULLLLLLLLLLLLLLLLLL"

  164. 47

    18

    663349316

    Returns: "UUUUUUUUUUUUUUURLRLLLLLRRLLLLLLLLRRRRRRLRR"

  165. 48

    642236991

    23

    Returns: "UUUUUUUUUUUUUUUUUUUUULLLLLLLLLLLLLLLLLLL"

  166. 49

    736233162

    16

    Returns: "UUUUUUUUUUUUUUUUUUUUUUUUUUUULLLLLLLLLLLL"

  167. 50

    6

    21

    Returns: "LLLLLLLLLLLLLLL"

  168. 50

    1

    1000000000

    Returns: "LLLRLLRRLLRLRRRLRLLRLRRRRLLRRRLRRR"

  169. 50

    1000000000

    1000000000

    Returns: ""

  170. 50

    1

    1

    Returns: ""

  171. 50

    1000000000

    1

    Returns: "UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU"

  172. 5

    12

    4

    Returns: "UUULR"

  173. 4

    1

    6

    Returns: "RL"

  174. 4

    4

    5

    Returns: "UUR"

  175. 50

    575

    1000000000

    Returns: "UUUUUUUUUUUUUUUUUUUUUUUURLLRRLLRLRRRLRLLRLRRRRLLRRRLRRR"

  176. 50

    2050

    2834873

    Returns: "UUUUUUUUUUUUUUUUUURLLLRLRRRRLLRLRLRRRL"

  177. 50

    987654321

    123456789

    Returns: "UUUUUUUUUUUUUUUUUUUUUUUUUUUUULLLRRRRRRRLRRRLLRRRRLRLLLLLLR"

  178. 4

    4

    8

    Returns: "UURRL"

  179. 30

    12323

    324

    Returns: "UUUUUUUUUUULLLLRRLLRRRRR"

  180. 4

    3

    6

    Returns: "UURL"

  181. 50

    500000000

    1000000000

    Returns: "UUUUUUUUUUUUUUUUUUUUUUUUUUUUUURLLRRLLRLRRRLRLLRLRRRRLLRRRLRRR"

  182. 50

    386222229

    668757381

    Returns: "UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUURRLLLRLRRRLLLRRLLRRLRLRRLLL"

  183. 48

    826569209

    13035880

    Returns: "UUUUUUUUUUUUUUUUUUUUUUUUUUUUULLLLRRLRLRRRRRRLLLRRLRRLRRRLR"

  184. 50

    126491973

    331160281

    Returns: "UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUURRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRLR"

  185. 50

    866988877

    866988878

    Returns: "UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUR"

  186. 2

    1

    3

    Returns: "R"

  187. 48

    423987

    2387407

    Returns: "UUUUUUUUUUUUUUUUUUUURRRRLRLRRRRLLLRLLR"

  188. 50

    100

    200

    Returns: "UUUUUUURLL"

  189. 42

    1

    100

    Returns: "LLLLLLLLLLLLLLLLRLLRRRL"

  190. 50

    500000

    1000000000

    Returns: "UUUUUUUUUUUUUUUUUUUUUUUUUUURLLRRLLRLRRRLRLLRLRRRRLLRRRLRRR"

  191. 3

    2

    1

    Returns: "U"

  192. 50

    423987

    2387407

    Returns: "UUUUUUUUUUUUUUUUUUUURRRRLRLRRRRLLLRLLLRRR"

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: