How Often Each Instruction Ran
A machine has a program of n instructions numbered 0 to n - 1 and a counter
that starts at 0.
ACC v move the counter on by 1
JMP v move the counter on by v
NOP v move the counter on by 1
HLT stop
The accumulator plays no part in this problem, so ACC behaves like NOP as
far as the counter is concerned. The machine performs at most s steps, and
one step is:
if the counter is outside 0 .. n-1, stop
otherwise execute the instruction at the counter, which counts as having run
An executed HLT stops the machine and still counts as having run. Print the
n execution counts in order on one line, separated by single spaces.
``` n = 3, s = 100: ACC 1 / JMP -1 / ACC 9
the counter goes 0, 1, 0, 1, ... forever, so the budget decides it: 100 steps split evenly between instructions 0 and 1, and instruction 2 is never reached. -> 50 50 0 ```
``` n = 4, s = 1: ACC 1 / ACC 2 / ACC 3 / HLT
exactly one step is affordable, so instruction 0 runs once and nothing else runs at all. -> 1 0 0 0 ```
## What most people try first
A loop that runs while the counter is in range, with the budget checked in the
wrong place, so the count is one too high or one too low. The second worked
example is the smallest input that tells the two apart: with a budget of one
step the answer is 1 0 0 0 and never 0 0 0 0 or 1 1 0 0.
The other common slip is not counting the HLT. It executes, so it runs, and a
declared test has a program whose HLT is reached with budget to spare.
## Why a budget is needed at all
The counter sequence here depends on nothing but the counter, so a program that
revisits an instruction is in a loop forever, exactly as in #2164. That means
the run either stops within n steps or never stops, and the first worked
example is the second case. The problem asks for counts rather than a verdict,
so the budget is what makes the answer finite: it is the number of steps whose
counts are being reported.
## The invariant that makes it right
At every point, the sum of all n counts equals the number of steps performed.
That is true because each step increments exactly one count, and it gives a
cheap check while writing the code: the counts must sum to s when the budget
ran out, and to something less than s when the program stopped on its own by
executing a HLT or by leaving the program.
## Overflow
A count is at most s, which is at most 10^5, so every count fits
comfortably in a 32 bit integer. The operands can be as large as 10^9, which
also fits, and they are never summed because the accumulator is not part of the
answer. Nothing here overflows, which is worth saying plainly rather than
leaving as a doubt.
## Cost
O(n + s) time and O(n) memory.