Real problems.
Your next challenge.

Problem summary

Interpret an EASY program on ten local registers R0…R9. Values wrap modulo 1000; each call starts with R0 equal to its argument and all other registers zero. MOV, ADD, SUB, MUL, DIV and MOD update their first register operand; division or remainder by zero gives zero. IFEQ, IFNEQ, IFG, IFL, IFGE and IFLE compare register or literal operands; a false condition skips to just after the next ENDIF. CALL recursively runs the same program with its operand, returning into the caller’s R9 without changing its other registers. RET returns its operand. Print the result or * for a nonterminating computation.

Constraints

1 ≤ L ≤ 100; 0 ≤ N < 1000; syntactically valid uppercase instructions and literals 0…999.

Worked example

An independently prepared example for this explanation.

3 5
ADD R0,7
MOV R9,R0
RET R9

12

Solution analysis

1. Parse operands and precompute the next ENDIF for each line, matching the statement’s next-ENDIF rule.
2. The whole program defines a deterministic function of its single argument, so memoize results for arguments 0…999.
3. Mark an argument active during evaluation. Re-entering an active argument means infinite recursion.
4. Execute register arithmetic modulo 1000; cache successful return values.

Why it works

Calls with identical arguments begin with identical local registers and follow the same deterministic computation. Re-entering an active call repeats its unfinished dependency and cannot terminate. Completed memoized calls can be replaced by their results without changing the caller. Between calls the instruction pointer only moves forward.

Watch out. Registers are local to each call, zero-divisor results are zero, and SUB wraps positively. Do not treat CALL as sharing all registers.

An independently written complete program with standard headers.

// Key idea: Calls with identical arguments begin with identical local registers and follow the same
// deterministic computation. Re-entering an active call repeats its unfinished dependency and cannot
// terminate.
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<limits>
#include<numeric>
#include<set>
#include<map>
#include<tuple>
#include<cstdint>
#include<functional>
#include<cmath>
using namespace std;
struct Ins{
    string op,a,b;
};
vector<Ins>p;
vector<int>skip;
int state[1000]={},memo[1000]={};
bool looped=false;
int solve(int argument){
    if(state[argument]==1){
        looped=true;
        return 0;
    }
    if(state[argument]==2){
        return memo[argument];
    }
    state[argument]=1;
    int r[10]={};
    r[0]=argument;
    auto value=[&](string s){
        return s[0]=='R'?r[s[1]-'0']:stoi(s);
    };
    for(int pc=0;pc<(int)p.size();pc++){
        auto in=p[pc];
        string op=in.op;
        if(op=="ENDIF"){
            continue;
        }
        int a=value(in.a);
        if(op=="RET"){
            state[argument]=2;
            return memo[argument]=a;
        }
        if(op=="CALL"){
            r[9]=solve(a);
            if(looped){
                return 0;
            }
            continue;
        }
        int b=value(in.b);
        if(op.rfind("IF",0)==0){
            bool yes=op=="IFEQ"?a==b
                :op=="IFNEQ"?a!=b
                :op=="IFG"?a>b
                :op=="IFL"?a<b
                :op=="IFGE"?a>=b
                                    :a<=b;
            if(!yes){
                pc=skip[pc];
            }
            continue;
        }
        int v=op=="MOV"?b
            :op=="ADD"?a+b
            :op=="SUB"?a-b
            :op=="MUL"?a*b
            :op=="DIV"?(b?a/b:0)
                            :(b?a%b:0);
        r[in.a[1]-'0']=(v%1000+1000)%1000;
    }
    return 0;
}
int main(){
    int l,n;
    cin>>l>>n;
    string line;
    getline(cin,line);
    p.resize(l);
    skip.resize(l);
    for(auto&in:p){
        getline(cin,line);
        auto space=line.find(' ');
        in.op=line.substr(0,space);
        if(space==string::npos){
            continue;
        }
        string rest=line.substr(space+1);
        rest.erase(remove(rest.begin(),rest.end(),' '),rest.end());
        auto comma=rest.find(',');
        in.a=rest.substr(0,comma);
        if(comma!=string::npos){
            in.b=rest.substr(comma+1);
        }
    }
    int next=l;
    for(int i=l-1;i>=0;i--){
        skip[i]=next;
        if(p[i].op=="ENDIF"){
            next=i;
        }
    }
    int answer=solve(n);
    if(looped){
        cout<<"*\n";
    }
    else{
        cout<<answer<<'\n';
    }
}