2166. Call, Return, and a Depth Limit

A machine has an accumulator, a program of n instructions numbered from 0, and a return stack that holds at most d addresses. The counter starts at 0, the accumulator at 0, and the stack empty.

ADD v add v to the accumulator, then move the counter on by 1 CALL a push the address counter+1 onto the return stack, then set the counter to a RET pop an address off the return stack and set the counter to it HLT stop

The machine performs at most s steps, and one step is: if the counter is outside 0 to n - 1, stop and report FAULT; otherwise execute the instruction there. Two instructions can fail instead of executing:

a CALL when the stack already holds d addresses -> OVERFLOW a RET when the stack is empty -> UNDERFLOW

A failed instruction does not execute, so it changes neither the accumulator nor the stack, and the run stops there.

Print one line with three things separated by single spaces: the outcome word, one of HALT, FAULT, OVERFLOW, UNDERFLOW or RUNNING; the accumulator; and the deepest the stack ever got.

``` n = 5, d = 4, s = 100: CALL 2 / HLT / ADD 5 / CALL 4 / RET

counter 0: CALL 2 pushes 1 and sets the counter to 2. stack [1] counter 2: ADD 5, accumulator 5, counter 3. counter 3: CALL 4 pushes 4 and sets the counter to 4. stack [1, 4] counter 4: RET pops 4, so the counter becomes 4 again, which is this same RET. stack [1] counter 4: RET pops 1, so the counter becomes 1. stack [] counter 1: HLT.

the deepest the stack ever got was 2. -> HALT 5 2 ```

``` n = 1, d = 0, s = 100: CALL 0

the stack can hold nothing at all, so the first CALL fails immediately and the deepest depth is 0. -> OVERFLOW 0 0 ```

## What most people try first

Pushing the target address instead of the return address. CALL a must push counter + 1, the instruction after the call, because that is where control resumes. Pushing a makes every RET jump back to the function it just entered, which looks like an infinite loop rather than a wrong answer, so it is easy to misdiagnose.

The second common slip is the order inside a CALL. The push uses the OLD counter plus one, and the counter is then overwritten. Writing the counter first and pushing afterwards pushes a + 1.

## Why the depth has to be tracked as it grows

The answer wants the deepest the stack ever got, not the depth at the end. The stack is empty again at every clean return, so reading its size after the run usually gives 0. Take the maximum each time you push, which is the only moment the depth can increase.

## Why a failed instruction must leave no trace

OVERFLOW and UNDERFLOW stop the run, and the statement says the failing instruction does not execute. That matters for the reported depth: on the second worked example a CALL that is refused must not be counted as having reached depth 1. It also means the accumulator is exactly what the previous instruction left.

The budget is checked before the fault, as in #2165: noticing that the counter has left the program costs a step, so a counter left outside by the last affordable step is RUNNING.

## Overflow

The accumulator is a sum of at most s operands of up to 10^9, with s as large as 10^5, so it can reach 10^14. A signed 32 bit integer stops at 2147483647, so the accumulator must be 64 bit. The depth is at most d, and the counter stays within the program or stops the run.

## Cost

O(n + s) time, and O(n + d) memory for the program and the stack.

Constraints - `1 ≤ n ≤ 2000` - `0 ≤ d ≤ 2000` - `1 ≤ s ≤ 100000` - each opcode is exactly `ADD`, `CALL`, `RET` or `HLT` - `-10^9 ≤ v ≤ 10^9` on `ADD` - `0 ≤ a < n` on `CALL` - a refused `CALL` or `RET` does not execute and changes nothing - the budget is checked before the counter is tested for a fault