Statistics

Problem Statement for "OneRegister"

Problem Statement

You've designed a computer and implemented all the common arithmetic operators: addition, subtraction, multiplication and integer division. However, your budget was very limited, so you could only afford to place a single register in the computer. The register can store any non-negative integer value. Since there is only one register, there is no need to identify the store location or the operands of each operation or its result. The programming language has four instructions: '+', '-', '*' and '/'. Each instruction performs the corresponding operation using the value in the register as both its parameters. It then stores the result in the same register, overwriting the previous content.

A program for your computer is a sequential list of zero or more instructions. You want to show that, even with its limitations, your newly constructed computer is powerful. You will be given two ints s and t. Return the shortest program that finishes with a value of t in the register if it contained s before executing. If there is more than one possible answer, return the one that comes earliest lexicographically. If there is no program that can do the job, return ":-(" (quotes for clarity) instead.

Definition

Class:
OneRegister
Method:
getProgram
Parameters:
int, int
Returns:
String
Method signature:
String getProgram(int s, int t)
(be sure your method is public)

Notes

  • A string comes lexicographically earlier than another one of the same length if and only if it contains a symbol with a lower ASCII code in the first position at which they differ. The operators in ascending order of ASCII code are: '*', '+', '-' and '/'.
  • If the division operation is used when the register contains a zero, the program will give an error and terminate with a zero value in the register.

Constraints

  • s and t will be between 1 and 1000000000 (10^9), inclusive.

Examples

  1. 7

    392

    Returns: "+*+"

    The program executes as follows: Reg | Ins | Res -----+-----+----- 7 | + | 14 14 | * | 196 196 | + | 392

  2. 7

    256

    Returns: "/+***"

  3. 4

    256

    Returns: "**"

  4. 7

    7

    Returns: ""

    A trivial program.

  5. 7

    9

    Returns: ":-("

    No solution.

  6. 10

    1

    Returns: "/"

  7. 5

    1250

    Returns: "**+"

  8. 4099

    4096

    Returns: "/+*+**"

  9. 1000000000

    536870912

    Returns: "/+*+*+**+"

  10. 11

    214358881

    Returns: "***"

  11. 1

    1

    Returns: ""

  12. 1

    2

    Returns: "+"

  13. 1

    4

    Returns: "+*"

  14. 1

    8

    Returns: "+*+"

  15. 1

    16

    Returns: "+**"

  16. 1

    128

    Returns: "+*+*+"

  17. 1

    256

    Returns: "+***"

  18. 1

    564

    Returns: ":-("

  19. 1

    65536

    Returns: "+****"

  20. 1

    262144

    Returns: "+***+*"

  21. 1

    1000000000

    Returns: ":-("

  22. 2

    256

    Returns: "***"

  23. 3

    4

    Returns: "/+*"

  24. 3

    16

    Returns: "/+**"

  25. 3

    59049

    Returns: ":-("

  26. 4

    2

    Returns: "/+"

  27. 5

    125

    Returns: ":-("

  28. 5

    6250000

    Returns: "*+**"

  29. 6

    144

    Returns: "+*"

  30. 8

    4

    Returns: "/+*"

  31. 8

    268435456

    Returns: "*+**"

  32. 9

    43046721

    Returns: "***"

  33. 9

    172186884

    Returns: "**+*"

  34. 10

    10245

    Returns: ":-("

  35. 10

    40000

    Returns: "*+*"

  36. 10

    100000000

    Returns: "***"

  37. 11

    214358881

    Returns: "***"

  38. 13

    456976

    Returns: "+**"

  39. 14

    802816

    Returns: "++++++*"

  40. 17

    83521

    Returns: "**"

  41. 18

    104976

    Returns: "**"

  42. 19

    16

    Returns: "/+**"

  43. 21

    168

    Returns: "+++"

  44. 22

    123904

    Returns: "++++*"

  45. 22

    234256

    Returns: "**"

  46. 23

    1083392

    Returns: "+++++*+"

  47. 23

    771751936

    Returns: "+++++++++++++++++++++++++"

  48. 27

    2916

    Returns: "+*"

  49. 28

    614656

    Returns: "**"

  50. 32

    1024

    Returns: "*"

  51. 32

    1048576

    Returns: "**"

  52. 33

    264

    Returns: "+++"

  53. 41

    2825761

    Returns: "**"

  54. 43

    172

    Returns: "++"

  55. 48

    73728

    Returns: "++*+"

  56. 49

    392

    Returns: "+++"

  57. 49

    5764801

    Returns: "**"

  58. 50

    838860800

    Returns: "++++++++++++++++++++++++"

  59. 51

    6765201

    Returns: "**"

  60. 53

    11236

    Returns: "+*"

  61. 53

    889192448

    Returns: "++++++++++++++++++++++++"

  62. 62

    260046848

    Returns: "++++++++++++++++++++++"

  63. 66

    18974736

    Returns: "**"

  64. 68

    21381376

    Returns: "**"

  65. 72

    1327104

    Returns: "++++*"

  66. 74

    592

    Returns: "+++"

  67. 74

    620756992

    Returns: "+++++++++++++++++++++++"

  68. 75

    31640625

    Returns: "**"

  69. 76

    46208

    Returns: "+*+"

  70. 80

    256

    Returns: "/+***"

  71. 80

    102400

    Returns: "++*"

  72. 81

    648

    Returns: "+++"

  73. 83

    881792

    Returns: "+++*+"

  74. 86

    875213056

    Returns: "+**"

  75. 92

    71639296

    Returns: "**"

  76. 94

    788529152

    Returns: "+++++++++++++++++++++++"

  77. 96

    768

    Returns: "+++"

  78. 96

    9437184

    Returns: "+++++*"

  79. 97

    88529281

    Returns: "**"

  80. 124

    64

    Returns: "/+*+*"

  81. 128

    96

    Returns: ":-("

  82. 157

    1024

    Returns: "/+**+*"

  83. 257

    256

    Returns: "/+***"

  84. 454

    256

    Returns: "/+***"

  85. 637

    512

    Returns: "/+***+"

  86. 43393

    65536

    Returns: "/+****"

  87. 68467

    68467

    Returns: ""

  88. 102968

    65536

    Returns: "/+****"

  89. 999999

    99999999

    Returns: ":-("

  90. 1002736

    1048576

    Returns: "/+**+**"

  91. 3431332

    2097152

    Returns: "/+**+**+"

  92. 30199283

    67108864

    Returns: "/+*+**+*"

  93. 193221366

    536870912

    Returns: "/+*+*+**+"

  94. 1000000000

    2

    Returns: "/+"

  95. 1000000000

    4

    Returns: "/+*"

  96. 1000000000

    16

    Returns: "/+**"

  97. 1000000000

    256

    Returns: "/+***"

  98. 1000000000

    65536

    Returns: "/+****"

  99. 1000000000

    1000000000

    Returns: ""

  100. 512

    65536

    Returns: "/+****"

    t is obtainable without division, but starting with division is faster.

  101. 10

    1000000000

    Returns: ":-("

  102. 465456

    16769023

    Returns: ":-("

  103. 4

    32768

    Returns: "+*+*+"

  104. 12345678

    260846532

    Returns: ":-("

  105. 29382974

    293829747

    Returns: ":-("

  106. 2

    1

    Returns: "/"

  107. 2

    4

    Returns: "*"

  108. 14

    12

    Returns: ":-("

  109. 666666670

    886389896

    Returns: ":-("

  110. 13

    999999999

    Returns: ":-("

  111. 65537

    131073

    Returns: ":-("

  112. 32

    64

    Returns: "+"

  113. 1

    99999999

    Returns: ":-("

  114. 5

    40000

    Returns: "+*+*"

  115. 5

    2

    Returns: "/+"

  116. 3

    9

    Returns: "*"

  117. 3

    6718464

    Returns: "+**+*"

  118. 77

    64

    Returns: "/+*+*"

  119. 1

    536870912

    Returns: "+*+*+**+"

  120. 7

    368947264

    Returns: "*+*+*"

  121. 7

    1

    Returns: "/"

  122. 3

    81

    Returns: "**"

  123. 350490028

    991619984

    Returns: ":-("

  124. 67

    1000000000

    Returns: ":-("

  125. 268435457

    536870913

    Returns: ":-("

  126. 10

    2

    Returns: "/+"

  127. 1000000000

    999999999

    Returns: ":-("

  128. 1

    1024

    Returns: "+**+*"

  129. 524288

    536870912

    Returns: "/+*+*+**+"

  130. 3

    402653184

    Returns: "+++++++++++++++++++++++++++"

  131. 7

    114688

    Returns: "++++++++++++++"

  132. 9

    36

    Returns: "++"

  133. 434

    134217728

    Returns: "/+*+**+*+"

  134. 1

    43

    Returns: ":-("

  135. 10

    4

    Returns: "/+*"

  136. 17

    16

    Returns: "/+**"

  137. 10889

    10

    Returns: ":-("

  138. 3

    805306368

    Returns: "++++++++++++++++++++++++++++"

  139. 12345

    2

    Returns: "/+"

  140. 3

    256

    Returns: "/+***"

  141. 999999999

    808348673

    Returns: ":-("

  142. 3

    60466176

    Returns: ":-("

  143. 7

    2048

    Returns: "/+**+*+"

  144. 128

    256

    Returns: "+"

  145. 8

    16

    Returns: "+"

  146. 7

    49

    Returns: "*"

  147. 162

    104976

    Returns: "+*"

  148. 1

    5

    Returns: ":-("

  149. 324987325

    382975023

    Returns: ":-("

  150. 3

    2

    Returns: "/+"

  151. 132

    2

    Returns: "/+"

  152. 1

    805306368

    Returns: ":-("

  153. 2

    6

    Returns: ":-("

  154. 65538

    262148

    Returns: ":-("

  155. 343

    33554432

    Returns: "/+*+***+"

  156. 3

    1000000000

    Returns: ":-("

  157. 77

    2097152

    Returns: "/+**+**+"

  158. 10000000

    1

    Returns: "/"

  159. 9

    589824

    Returns: "++++++++++++++++"

  160. 10000

    100000000

    Returns: "*"

  161. 6

    787346436

    Returns: ":-("

  162. 536870913

    536870912

    Returns: "/+*+*+**+"

  163. 50

    100

    Returns: "+"

  164. 7

    1000000000

    Returns: ":-("

  165. 7

    8

    Returns: "/+*+"

  166. 500000000

    1000000000

    Returns: "+"

  167. 7

    268435456

    Returns: "/+*+*+**"

  168. 3

    11

    Returns: ":-("

  169. 6

    18

    Returns: ":-("

  170. 16384

    134217728

    Returns: "/+*+**+*+"

  171. 256

    1024

    Returns: "++"

  172. 1

    64

    Returns: "+*+*"

  173. 17

    8

    Returns: "/+*+"

  174. 31000

    961000000

    Returns: "*"

  175. 512

    131072

    Returns: "/+****+"

  176. 500000

    891896832

    Returns: ":-("

  177. 3

    536870912

    Returns: "/+*+*+**+"

  178. 1024

    65536

    Returns: "++++++"

  179. 5

    83886080

    Returns: "++++++++++++++++++++++++"

  180. 64

    256

    Returns: "++"

  181. 7

    14680064

    Returns: "+++++++++++++++++++++"

  182. 2

    67108864

    Returns: "*+**+*"

  183. 1

    3

    Returns: ":-("

  184. 65500

    70000

    Returns: ":-("

  185. 3

    65536

    Returns: "/+****"

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: