Statistics

Problem Statement for "OneInstructionOnly"

Problem Statement

Assembly languages usually have a small collection of instructions to add, compare, store data into memory, and so on.

But some instructions are so powerful that a single instruction is enough to write any program at all.


The memory of our program is a finite array memory[0..M-1]. Each element of memory is an integer. (Initially these integers must be non-negative and small, but during the run of your program they may become negative and/or big.)

The content of this memory is both your program and your data.


The only instruction you can use in your program is the instruction "take one cell of memory, subtract the value of another cell from it, and if the result is zero or negative, jump".

Each instruction takes three arguments: three indices into memory. Thus, usually a program is a sequence of triples of integers (but much wilder things including self-overwriting programs are possible).


Here is a full interpreter of this language, written in Python. The input is a sequence of integers: the initial content of the array memory[]. 


    #############################################################

    import sys

    memory = [ int(x) for x in sys.stdin.read().split() ]
    try:
        while True:
            ip = memory[0]
            a, b, c = memory[ip], memory[ip+1], memory[ip+2]
            memory[a] -= memory[b]
            if memory[a] <= 0: memory[0] = c
            else: memory[0] += 3
    except:
        print( memory[1] )

    #############################################################

Explanation:

The cell memory[0] stores the instruction pointer (below also denoted "ip").

The execution of your program is a potentially infinite loop that looks as follows.

  1. Look at memory[0] to read the current ip.
  2. Look at the values a = memory[ip], b = memory[ip+1], and c = memory[ip+2].
  3. Subtract memory[b] from memory[a].
  4. If memory[a] is now zero or negative, set ip to c (jump to that address), otherwise increment ip by 3 (move to the next triple).

Execution ends if your program tries to access a value outside the existing memory. The output is the value memory[1] at the end of the run.


----------------------------


Your task is to implement exponentiation (more precisely, a very small number taken to a moderately large power) in this "programming language".

You are given integers A and B. Construct and return any int[] memory with the following properties:

  • memory[] must have between 2 and 70 elements, inclusive.
  • Initially, each element of memory[] must be between 0 and 20,000, inclusive.
  • When executed on your memory[], the interpreter must terminate in at most 200,000 steps.
  • During the execution of the program the values in your memory must not underflow -(10^5000) or overflow 10^5000.
  • The returned value must be A to the power of B.

Definition

Class:
OneInstructionOnly
Method:
program
Parameters:
int, int
Returns:
int[]
Method signature:
int[] program(int A, int B)
(be sure your method is public)

Notes

  • The step during which your solution makes an invalid memory access and terminates is not counted.

Constraints

  • A will be between 0 and 7, inclusive.
  • B will be between 1 and 20,000, inclusive.
  • A to the power of B will not exceed 10^5000.

Examples

  1. 7

    1

    Returns: {42, 7 }

    The program is supposed to return 7^1 = 7. Our program will finish in 0 steps: already in the beginning the instruction pointer points outside our memory, so the program terminates and the value memory[1] = 7 is returned.

  2. 3

    7

    Returns: {4, 2185, 1, 0, 3, 2, 8, 1000, 1, 3, 0, 1, 3, 0, 4242 }

    This program will execute three steps and then terminate. The very first step looks as follows: We have ip = 4. We take a=memory[4], b=memory[5], c=memory[6]. We have a=3, b=2, c=8. We subtract memory[b] from memory[a]. Thus, memory[3] is now equal to 0 - 1 = (-1). As the new value is <= 0, we set ip to c = 8. Memory now looks as follows: {8, 2185, 1, -1, 3, 2, 8, 1000, 1, 3, 0, 1, 3, 0, 4242 } Second step: As ip=8, we take a=memory[8], b=memory[9], and c=memory[10]. We then perform memory[a] -= memory[b], and as the result is positive, we don't jump: ip is incremented from 8 to 11. Third step: As ip=11, we take a=memory[11], b=memory[12], and c=memory[13]. Again we subtract, again the result is positive, and so ip is incremented to 14. Attempted but not executed fourth step: As ip=14, we try to take a=memory[14], b=memory[15], and c=memory[16]. The indices 15 and 16 are not valid indices into memory, thus the execution of our program terminates after three steps, and the current content of memory[1] is returned. Note that even if memory did have two more cells, the program would still terminate here, as now a=4242 is not a valid index into memory.

  3. 1

    1

    Returns: {42, 1 }

  4. 1

    1000

    Returns: {42, 1 }

  5. 7

    1

    Returns: {42, 7 }

  6. 1

    2

    Returns: {42, 1 }

  7. 2

    1

    Returns: {5, 2, 1, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 3, 3, 5 }

  8. 2

    2

    Returns: {5, 2, 2, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 3, 3, 5 }

  9. 2

    3

    Returns: {5, 2, 3, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 3, 3, 5 }

  10. 3

    2

    Returns: {5, 3, 2, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 3, 3, 5 }

  11. 2

    4

    Returns: {5, 2, 4, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 3, 3, 5 }

  12. 3

    3

    Returns: {5, 3, 3, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 3, 3, 5 }

  13. 4

    2

    Returns: {5, 4, 2, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  14. 0

    1

    Returns: {42, 0 }

  15. 0

    20000

    Returns: {42, 0 }

  16. 1

    20000

    Returns: {42, 1 }

  17. 0

    17

    Returns: {42, 0 }

  18. 2

    16609

    Returns: {5, 2, 16609, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 3, 3, 5 }

  19. 2

    15668

    Returns: {5, 2, 15668, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 3, 3, 5 }

  20. 2

    15076

    Returns: {5, 2, 15076, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 3, 3, 5 }

  21. 2

    15829

    Returns: {5, 2, 15829, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 3, 3, 5 }

  22. 2

    16081

    Returns: {5, 2, 16081, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 3, 3, 5 }

  23. 2

    15877

    Returns: {5, 2, 15877, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 3, 3, 5 }

  24. 2

    16116

    Returns: {5, 2, 16116, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 3, 3, 5 }

  25. 2

    5628

    Returns: {5, 2, 5628, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 3, 3, 5 }

  26. 2

    4218

    Returns: {5, 2, 4218, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 3, 3, 5 }

  27. 2

    8396

    Returns: {5, 2, 8396, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 3, 3, 5 }

  28. 2

    6334

    Returns: {5, 2, 6334, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 3, 3, 5 }

  29. 2

    6430

    Returns: {5, 2, 6430, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 3, 3, 5 }

  30. 2

    10086

    Returns: {5, 2, 10086, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 3, 3, 5 }

  31. 3

    10479

    Returns: {5, 3, 10479, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 3, 3, 5 }

  32. 3

    9514

    Returns: {5, 3, 9514, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 3, 3, 5 }

  33. 3

    10288

    Returns: {5, 3, 10288, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 3, 3, 5 }

  34. 3

    9479

    Returns: {5, 3, 9479, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 3, 3, 5 }

  35. 3

    9640

    Returns: {5, 3, 9640, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 3, 3, 5 }

  36. 3

    9432

    Returns: {5, 3, 9432, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 3, 3, 5 }

  37. 3

    9971

    Returns: {5, 3, 9971, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 3, 3, 5 }

  38. 3

    7890

    Returns: {5, 3, 7890, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 3, 3, 5 }

  39. 3

    8957

    Returns: {5, 3, 8957, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 3, 3, 5 }

  40. 3

    150

    Returns: {5, 3, 150, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 3, 3, 5 }

  41. 3

    5171

    Returns: {5, 3, 5171, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 3, 3, 5 }

  42. 3

    9300

    Returns: {5, 3, 9300, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 3, 3, 5 }

  43. 3

    7008

    Returns: {5, 3, 7008, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 3, 3, 5 }

  44. 4

    8304

    Returns: {5, 4, 8304, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  45. 4

    7708

    Returns: {5, 4, 7708, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  46. 4

    7716

    Returns: {5, 4, 7716, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  47. 4

    8008

    Returns: {5, 4, 8008, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  48. 4

    7999

    Returns: {5, 4, 7999, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  49. 4

    7840

    Returns: {5, 4, 7840, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  50. 4

    7925

    Returns: {5, 4, 7925, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  51. 4

    1983

    Returns: {5, 4, 1983, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  52. 4

    273

    Returns: {5, 4, 273, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  53. 4

    4596

    Returns: {5, 4, 4596, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  54. 4

    3066

    Returns: {5, 4, 3066, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  55. 4

    5872

    Returns: {5, 4, 5872, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  56. 4

    5633

    Returns: {5, 4, 5633, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  57. 5

    7153

    Returns: {5, 5, 7153, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  58. 5

    6798

    Returns: {5, 5, 6798, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  59. 5

    7052

    Returns: {5, 5, 7052, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  60. 5

    6787

    Returns: {5, 5, 6787, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  61. 5

    7008

    Returns: {5, 5, 7008, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  62. 5

    7025

    Returns: {5, 5, 7025, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  63. 5

    6637

    Returns: {5, 5, 6637, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  64. 5

    1955

    Returns: {5, 5, 1955, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  65. 5

    5974

    Returns: {5, 5, 5974, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  66. 5

    290

    Returns: {5, 5, 290, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  67. 5

    1029

    Returns: {5, 5, 1029, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  68. 5

    2736

    Returns: {5, 5, 2736, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  69. 5

    803

    Returns: {5, 5, 803, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  70. 6

    6425

    Returns: {5, 6, 6425, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  71. 6

    6153

    Returns: {5, 6, 6153, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  72. 6

    6374

    Returns: {5, 6, 6374, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  73. 6

    6174

    Returns: {5, 6, 6174, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  74. 6

    6302

    Returns: {5, 6, 6302, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  75. 6

    6335

    Returns: {5, 6, 6335, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  76. 6

    6040

    Returns: {5, 6, 6040, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  77. 6

    796

    Returns: {5, 6, 796, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  78. 6

    5316

    Returns: {5, 6, 5316, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  79. 6

    1860

    Returns: {5, 6, 1860, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  80. 6

    5728

    Returns: {5, 6, 5728, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  81. 6

    2744

    Returns: {5, 6, 2744, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  82. 6

    1791

    Returns: {5, 6, 1791, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  83. 7

    5916

    Returns: {5, 7, 5916, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 1, 3, 0, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  84. 7

    5806

    Returns: {5, 7, 5806, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 1, 3, 0, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  85. 7

    5436

    Returns: {5, 7, 5436, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 1, 3, 0, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  86. 7

    5750

    Returns: {5, 7, 5750, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 1, 3, 0, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  87. 7

    5685

    Returns: {5, 7, 5685, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 1, 3, 0, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  88. 7

    5617

    Returns: {5, 7, 5617, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 1, 3, 0, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  89. 7

    5568

    Returns: {5, 7, 5568, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 1, 3, 0, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  90. 7

    4549

    Returns: {5, 7, 4549, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 1, 3, 0, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  91. 7

    2143

    Returns: {5, 7, 2143, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 1, 3, 0, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  92. 7

    2925

    Returns: {5, 7, 2925, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 1, 3, 0, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  93. 7

    4364

    Returns: {5, 7, 4364, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 1, 3, 0, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  94. 7

    4632

    Returns: {5, 7, 4632, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 1, 3, 0, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  95. 7

    329

    Returns: {5, 7, 329, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 1, 3, 0, 1, 3, 0, 1, 3, 0, 1, 3, 0, 1, 3, 0, 3, 3, 5 }

  96. 2

    14728

    Returns: {5, 2, 14728, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 3, 3, 5 }

  97. 2

    13543

    Returns: {5, 2, 13543, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 3, 3, 5 }

  98. 2

    15049

    Returns: {5, 2, 15049, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 3, 3, 5 }

  99. 2

    15554

    Returns: {5, 2, 15554, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 3, 3, 5 }

  100. 2

    15145

    Returns: {5, 2, 15145, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 3, 3, 5 }

  101. 2

    15624

    Returns: {5, 2, 15624, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 3, 3, 5 }

  102. 2

    14693

    Returns: {5, 2, 14693, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 3, 3, 5 }

  103. 2

    16383

    Returns: {5, 2, 16383, 0, 1, 2, 4, 999, 3, 1, 11, 1, 3, 14, 3, 3, 5 }

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: