2170. 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.

Constraints - `1 ≤ n ≤ 2000` - `1 ≤ s ≤ 100000` - each opcode is exactly `ACC`, `JMP`, `NOP` or `HLT` - `-10^9 ≤ v ≤ 10^9` - an executed `HLT` stops the machine and counts as having run - the counter leaving the range 0 to `n - 1` stops the machine