Statistics

Problem Statement for "ClassicTowers"

Problem Statement

This problem is related to the classic "Tower of Hanoi" puzzle. The puzzle consists of three rods and n disks. The rods are labeled A, B, and C. The disks all have different sizes, and they are numbered 0 through n-1 from smallest to largest.

In a valid configuration, each disk is placed onto one of the three rods and on each rod the disks are ordered by size: smallest to largest from top to bottom. In order to specify a configuration we just need to specify the rod for each disk, as the order of disks on each rod is uniquely determined by their sizes.

A valid move is a move in which we take the topmost disk from one of the rods and place it onto the top of the disks on another rod in a way that produces a valid configuration. That is, given a valid configuration, a move is only valid if a) you are moving the topmost disk from one rod onto another rod that is currently empty, or b) the disk you are moving is smaller than the current topmost disk on the destination rod.

A solution is a sequence of valid moves that produces a configuration in which all n disks are in a single stack on an arbitrary rod.

You are given a int[] count with three elements and an int k. Construct any valid configuration with the following properties:

  • There are exactly count[0] disks on rod A.
  • There are exactly count[1] disks on rod B.
  • There are exactly count[2] disks on rod C.
  • The shortest solution for this configuration consists of exactly k moves.

If there is no such configuration, return an empty String. Otherwise, return a String with n = sum(count) characters. For each valid i, character i of the return value should be the name of the rod where disk i is placed. If there are multiple possible solutions, you may return any of them.

Definition

Class:
ClassicTowers
Method:
findTowers
Parameters:
long, int[]
Returns:
String
Method signature:
String findTowers(long k, int[] count)
(be sure your method is public)

Constraints

  • k will be between 0 and 2^50 - 1, inclusive.
  • count will have exactly 3 elements.
  • Each element of count will be between 0 and 50.
  • The sum of elements in count will be between 1 and 50, inclusive.
  • Elements in count will be in a non-decreasing order.

Examples

  1. 4

    {1,1,2}

    Returns: "CCAB"

    The returned value represents disk 0 and 1 on rod C, disk 2 on rod A, and disk 3 on rod B. Here, we can put all disks onto rod B as follows: Move disk 2 onto rod B. Move disk 0 onto rod A. Move disk 1 onto rod B. Move disk 0 onto rod B.

  2. 0

    {0, 0, 50}

    Returns: "CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC"

    The return value represents all disks on rod C.

  3. 0

    {10,20,20}

    Returns: ""

    This is impossible. A configuration with some disks on each rod clearly doesn't have any solution with 0 moves.

  4. 123456123456123

    {10,10,30}

    Returns: "CCACCCACCABACCABBACCCBBCCBCCCBACCCCABBACCCCCACBCCC"

  5. 314159265358979

    {15,16,17}

    Returns: ""

  6. 3324

    {4,4,5}

    Returns: "CCAAAABBCCBBC"

  7. 955671075128

    {10,15,18}

    Returns: "AAABAACCABBABABCBBBBCBCBBACCCCCABCCCCBCBCCC"

  8. 15322486

    {1,9,15}

    Returns: ""

  9. 4

    {0,1,5}

    Returns: ""

  10. 5349863

    {2,8,15}

    Returns: "CCBCCBCCBCCCCABCBCCCBACBB"

  11. 231503

    {6,6,7}

    Returns: "BAAABBACCCCABBBCCAC"

  12. 5281413

    {2,12,13}

    Returns: ""

  13. 1414

    {0,3,8}

    Returns: ""

  14. 2

    {0,2,5}

    Returns: ""

  15. 105317

    {3,4,12}

    Returns: ""

  16. 28457

    {4,8,8}

    Returns: "BCCABACCACCACBCBBBBB"

  17. 1232333792

    {6,14,18}

    Returns: "BBBBBABBBBCABCCCCACCBCCABCCABBACCCCCCC"

  18. 706

    {3,4,5}

    Returns: "ABCCCCBBCBAA"

  19. 2041

    {6,15,21}

    Returns: ""

  20. 98259

    {1,4,19}

    Returns: ""

  21. 2

    {0,1,2}

    Returns: ""

  22. 3086

    {1,4,10}

    Returns: ""

  23. 162628

    {4,7,8}

    Returns: "AABCCCABCCBCBBBCCAB"

  24. 3129526

    {3,4,20}

    Returns: "BCCBCCBACCCCCCACCCCCABCCCCC"

  25. 1026209

    {3,8,10}

    Returns: "BCCCCBABCCCBABCACBBBC"

  26. 13

    {0,3,5}

    Returns: "BCBBCCCC"

  27. 129274921985

    {9,15,18}

    Returns: "BCCCCCCCCCABBBCBCABBBAABACCAACCCCAABCBBBBB"

  28. 1404631608

    {2,13,17}

    Returns: ""

  29. 2

    {0,0,3}

    Returns: ""

  30. 3

    {0,2,4}

    Returns: "BBCCCC"

  31. 2420

    {0,3,13}

    Returns: ""

  32. 15525654419

    {4,9,25}

    Returns: ""

  33. 0

    {0,0,1}

    Returns: "C"

  34. 2351631271

    {2,5,31}

    Returns: ""

  35. 117435798012

    {9,13,20}

    Returns: "AABAAAABCBBBACCCCCCACBCBBBCBCACBCCBCBCCCCC"

  36. 1

    {2,3,6}

    Returns: ""

  37. 51411511

    {4,9,14}

    Returns: "BAACBBCCCABCCCBCCCCCABBBCBC"

  38. 0

    {0,0,2}

    Returns: "CC"

  39. 1

    {0,1,1}

    Returns: "BC"

  40. 35600

    {2,5,15}

    Returns: ""

  41. 580817

    {5,6,10}

    Returns: "BCCCABABAACCCBCBCCCAB"

  42. 10541757

    {6,7,19}

    Returns: "BCAAAACBACBCCBCBCCCCCBABCCCCCCCC"

  43. 433

    {3,3,4}

    Returns: "BCCCACABAB"

  44. 42

    {0,3,4}

    Returns: ""

  45. 43644973390093

    {13,16,19}

    Returns: "BCAACCCCABBAABBACABBBACCAACCCAABBCCCBBCBCCBCCABB"

  46. 10878

    {1,6,10}

    Returns: ""

  47. 168

    {3,3,4}

    Returns: "CCCABACABB"

  48. 43667

    {6,6,10}

    Returns: "BABBACCABACABCABCCCCCC"

  49. 2

    {3,6,18}

    Returns: ""

  50. 1632168366

    {6,11,16}

    Returns: "ABACABCBBCCBACCBCCCABBCABCCCCBBCC"

  51. 468900928463

    {1,15,23}

    Returns: ""

  52. 7

    {0,1,3}

    Returns: "CCBC"

  53. 4402989

    {3,9,15}

    Returns: "CBCCBACCBCCCBACCBCBBBBACCCC"

  54. 144

    {5,5,9}

    Returns: ""

  55. 41871052457651

    {0,15,33}

    Returns: ""

  56. 2135122886294

    {11,11,20}

    Returns: "ABABACCABAAABBCBCBCCCBCCACCCBCCCBAAACCCCBC"

  57. 1953123810

    {0,5,27}

    Returns: ""

  58. 276808811723906

    {10,13,26}

    Returns: "ABCCCCCABBAAABABCCABBCCCABCCABBCBCCCCCBCCCBCCCCAC"

  59. 1

    {14,15,18}

    Returns: ""

  60. 265224367831067

    {9,17,24}

    Returns: "BABAABBBBBBABCCBCABCCACCCCBCCABCCCCACCBBACCCBCCBCC"

  61. 533118936

    {5,10,18}

    Returns: "BBBAABABBBCCCCACBCBCCCACCCCCBCCCC"

  62. 72023576925986

    {11,15,24}

    Returns: "ABCCCABBAAACABABCCBCBCBCCCABCCABACCCCCCBBCCCCCABBB"

  63. 932825390878

    {9,13,22}

    Returns: "ABAAABBBAACCCACCBCCBCCABCCCCBBCCABBCCBCBCCCC"

  64. 44842434

    {2,11,15}

    Returns: ""

  65. 502596080253

    {0,2,44}

    Returns: ""

  66. 231869976397

    {10,12,20}

    Returns: "BCAACCABAAAABBBBABBCCCCABBCCCCCCCACBCBCCCC"

  67. 81488402476426

    {12,19,19}

    Returns: "ABCABBBAABAABCBCCCCABBACBBBCCCCBCCACCBBBBACABBACCC"

  68. 33676073711

    {8,10,18}

    Returns: "BAAABAACABCBBCCCCCCCCCBABBCBCACCCCBC"

  69. 58369028627

    {5,17,24}

    Returns: "CBCCABBBBACCBBCABBBBACCCBCCABCCBBCBBCCCCCCCCCC"

  70. 15125049447760

    {7,18,20}

    Returns: "BBBBACABACABACCCBBCCBBCCBBCCABBCBCCCCCACBCBBC"

  71. 49539306

    {1,10,19}

    Returns: ""

  72. 16389808312669

    {6,15,24}

    Returns: "BCACBCBABCCCABCBBBCCBBCABBCBCCCCCCCABCCCACCBC"

  73. 1370861761317

    {5,20,22}

    Returns: ""

  74. 521

    {11,12,27}

    Returns: ""

  75. 358269762196

    {3,15,22}

    Returns: ""

  76. 24581062110698

    {10,18,20}

    Returns: "ABCABAACBCACABCBBCCBBBBCABBCCACCBBCBCBACCBCBACCC"

  77. 51571547754009

    {2,14,34}

    Returns: ""

  78. 264524807301495

    {11,18,20}

    Returns: "BAACAAABACCABCBCCCBBCABBCBCBBBBCABCACBBACCCCBCCBC"

  79. 428558589

    {0,22,25}

    Returns: ""

  80. 268564627306

    {0,13,33}

    Returns: ""

  81. 53413045801858

    {9,15,23}

    Returns: "ABCCCCCAAABBACCCACBBBCCBCBBBCBCCCCABCAABCCCCBBC"

  82. 100408840131

    {8,14,19}

    Returns: "BABBBBAAAACBCCBABCBACBCBCCCCCBCBCCCABCCCC"

  83. 21023857259889

    {13,14,19}

    Returns: "BCCCAAABACABAABBAABACCCBBBBBCCCCACCCACCCBBCCAB"

  84. 62716763308236

    {7,20,23}

    Returns: "AABABBCBCCCCCCCCCBBCCBBCCABBBCBCCBACBBBBCAABBBCCCC"

  85. 158277320227

    {4,12,27}

    Returns: ""

  86. 22669115493324

    {0,24,25}

    Returns: ""

  87. 21302

    {2,6,11}

    Returns: "BCCBCBCCBBCCABACCCC"

  88. 498003152961

    {3,16,21}

    Returns: ""

  89. 31446884684404

    {11,16,20}

    Returns: "AABCAAABBCAABCCCCCABBCBCCCBBCCACBCCBBCCABBABBCC"

  90. 33684304921378

    {5,13,30}

    Returns: "ABCCCABBCBCCCCCBCCBCCCCCABCCCBCBABCCCBACBCCCBCCC"

  91. 11663884752868

    {10,14,25}

    Returns: "AABCCAABBBCBACCCBABCBCBCCBCACCACCCBCBCCABCABCCCCC"

  92. 8842062711

    {7,12,16}

    Returns: "BAACACBCBBCABACCACBCCCCCBCCCBBBBBAC"

  93. 19662640994878

    {5,21,24}

    Returns: ""

  94. 10449740246721

    {10,18,22}

    Returns: "BCCCCCAACAAABACCCACBCCCCBABCCCCCABBBBBBCBCCABBBBBB"

  95. 86439663189667

    {4,13,32}

    Returns: ""

  96. 31352529

    {4,9,15}

    Returns: "BCCCABAABCBCCBBCCBCCBCACBCCC"

  97. 240888086502314

    {6,15,28}

    Returns: "BCACBCACCCBCBCCACBCCABCBCCCCCABBBCCBACCCBCBCCBCBC"

  98. 23377247136081

    {12,12,22}

    Returns: "BCCCABACABBACACCBACCCCCABBBBCCCCBACCCCABACABAC"

  99. 51743197524

    {5,19,24}

    Returns: "BBCABCBABCCABBBCACBBBACCCCBCBBBBBBCBCCCCCCCCCCCC"

  100. 554389358122

    {6,12,24}

    Returns: ""

  101. 40048343526

    {1,13,24}

    Returns: ""

  102. 7107449876

    {1,16,20}

    Returns: ""

  103. 48773119528845

    {7,15,25}

    Returns: "BCAACCCACBBBCCBBCBBCACBCCCCCCACBBCBCCBACCCBCBAC"

  104. 325

    {1,19,29}

    Returns: ""

  105. 6237529119

    {7,8,26}

    Returns: "ACCCBCCCCCABBACCABBACCBCCBCCACCBACCCCCCCC"

  106. 524464778747854

    {3,20,27}

    Returns: ""

  107. 255329954233

    {8,12,19}

    Returns: "BCCAAABCBCCABCBBBCCBBCACABCCACCBCCBCCAC"

  108. 273685107993949

    {11,17,21}

    Returns: "BCAAABACABCBCBBCCCABBACBBBBCCCABBACBACCBCCCACCCBC"

  109. 1489658358

    {5,15,15}

    Returns: "ABABABBBBCCCCBBCCBABCCBCBBBCCBACCCC"

  110. 89758140059

    {11,12,18}

    Returns: "BABAABBACACAAAABCCCCCCCCCBBCCBBABBCABCCCC"

  111. 999848274

    {11,11,12}

    Returns: "ABCCABACABBAAAABBBBAABBCCCACCBCCCC"

  112. 7944090126

    {2,11,22}

    Returns: ""

  113. 16579246500

    {10,12,15}

    Returns: "AABCCBABABBAAACCAACCBBCCCCACBCBBBBCCC"

  114. 87242445729

    {10,15,22}

    Returns: "BCCCCABAAACCBAAAACCCBBBBBBBBCACBBBCABCCCCCCCCCC"

  115. 6412487188810

    {8,16,22}

    Returns: "ABCABBACABBBBCBCBABCCCCCCBBCCCCCABCABCBCCABCCC"

  116. 29014744114345

    {12,15,23}

    Returns: "BCCABACABBACCABBBBACCCCAACABBBBCCACCCBBCCBACACCCCC"

  117. 451196496649125

    {7,20,23}

    Returns: "BCABBACACBCBBCCCCCCBABBBCBBBCBACCCBCCABCCABCBCCBBC"

  118. 14328529804575

    {8,19,23}

    Returns: "BAABBCCCABABBCACBCBBCACBCBCCCBBBBBBACCCCABCBCCCCCC"

  119. 70

    {9,13,28}

    Returns: ""

  120. 70386904868724

    {13,18,19}

    Returns: "AABCAAABAAACCABBBCCBABBCCBABBCBBBBACCCCCCCCCCCABBB"

  121. 163476270883057

    {13,15,22}

    Returns: "BCCCAAAACCCCCABBBABBCCCCABBACCABBCCACBABCCBACBBACC"

  122. 517785373897100

    {2,17,31}

    Returns: ""

  123. 533320764267574

    {12,12,26}

    Returns: "ABABCBCCCCACBCCABBACACACBCACBCCBCACACCCCABACCBCCBC"

  124. 1175050481

    {9,9,32}

    Returns: "BCCCAAAACCCAACBBABBACCCCCBCBBBACCCCCCCCCCCCCCCCCCC"

  125. 14737021618

    {0,22,28}

    Returns: ""

  126. 58202440

    {0,7,20}

    Returns: ""

  127. 3599194184

    {3,10,26}

    Returns: ""

  128. 25

    {1,2,5}

    Returns: "ACCBBCCC"

  129. 418654

    {0,9,13}

    Returns: ""

  130. 15

    {0,1,3}

    Returns: ""

  131. 478

    {1,3,5}

    Returns: ""

  132. 4158214059

    {8,9,15}

    Returns: ""

  133. 66039166

    {2,11,13}

    Returns: ""

  134. 2449

    {0,8,13}

    Returns: ""

  135. 69919340

    {6,9,14}

    Returns: "BBCBCACAABCCCBCCACBCABCCCCABB"

  136. 684

    {1,3,7}

    Returns: ""

  137. 0

    {0,0,1}

    Returns: "C"

  138. 31659

    {3,6,6}

    Returns: ""

  139. 2122081

    {5,7,13}

    Returns: "BCCCCACACBBBBCBCCCCCCBAAA"

  140. 8053022

    {1,5,21}

    Returns: ""

  141. 42

    {1,2,3}

    Returns: ""

  142. 3

    {0,1,1}

    Returns: ""

  143. 142297260952

    {7,10,25}

    Returns: ""

  144. 2185

    {2,3,21}

    Returns: ""

  145. 619655050657

    {6,15,19}

    Returns: ""

  146. 554914039

    {6,8,17}

    Returns: "CCBCACCACCCCBACBCBCCABBBACCCCAB"

  147. 29939335960814

    {9,18,21}

    Returns: "ABAACAAABBBCBCCCCCACBBBCBBCABBCBCBACCBCCBCBCBCCC"

  148. 2

    {0,1,2}

    Returns: ""

  149. 33

    {2,3,4}

    Returns: "ACCCCABBB"

  150. 976465

    {2,11,11}

    Returns: "BCCCBABCCBBCCBBBABBBCCCC"

  151. 1803846225

    {8,9,14}

    Returns: ""

  152. 2

    {0,1,1}

    Returns: ""

  153. 120

    {0,3,4}

    Returns: ""

  154. 411

    {8,16,19}

    Returns: ""

  155. 30

    {0,2,3}

    Returns: ""

  156. 123456123456123

    {10, 10, 30 }

    Returns: "CCACCCACCABACCABBACCCBBCCBCCCBACCCCABBACCCCCACBCCC"

  157. 357913938

    {10, 10, 10 }

    Returns: "ABCCABACABACABCABCBABCBACBCABC"

  158. 15

    {0, 0, 4 }

    Returns: ""

  159. 0

    {0, 0, 1 }

    Returns: "C"

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: