Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

プログラム停止判定

皆さんは、苦労して作ったプログラムを実行してみたら、無限ループになってしまった経験はありませんか？ プログラムの実行が停止するかどうかを、実行しなくても事前に判定できると便利ですよね。

残念ながら、皆さんがふだん使っているプログラミング言語では、あらゆるプログラムに対してそのような判定をすることは不可能です。しかし、それよりもはるかに計算能力の低いプログラミング言語なら、その言語で書いたプログラムが停止するかどうかを判定するプログラムを書ける場合があります。

TinyPowerというプログラミング言語を考えます。この言語のプログラムは行の並びです。プログラムの各行には、先頭に行番号を書き、その後ろに文を一つ書きます。この言語で書ける文の種類は以下の通りです。

  

    文の種類
    動作
  

  

    ADD var1 var2 var3
    変数 var2 の値と var3 の値を加算した結果を変数 var1に代入する
  

  

    ADD var1 var2 con
    変数 var2 の値と定数 con を加算した結果を変数 var1 に代入する
  

  

    SUB var1 var2 var3
    変数 var2 の値から var3 の値を減算した結果を変数 var1 に代入する
  

  

    SUB var1 var2 con
    変数 var2 の値から定数 con を減算した結果を変数 var1 に代入する
  

  

    SET var1 var2
    変数 var2の値を変数 var1 に代入する
  

  

    SET var1 con
    定数 con を変数 var1 に代入する
  

  

    IF var1 dest
    変数 var1 の値が０でないときだけ、行番号 dest にジャンプする
  

  

    HALT
    プログラムを停止させる
  

行番号は正の整数で、プログラム中に同じ行番号が２つ以上現れることはありません。変数は英小文字一文字で表し、定数と変数の値は整数です。変数の宣言は不要で、変数の初期値は０です。

プログラムの実行は先頭の文から始まり、並んでいる順に文が実行されます。ただし、上の表に書かれたように、IF文の変数の値が０でないときは、変数の後ろに書かれた行番号で指定される行にジャンプし、その行に書かれた文から実行を続けます。プログラムは以下のときに停止します。

 HALT文を実行したとき。

 負の整数または１６以上の整数を変数に代入しようとしたとき（変数の値は更新されない）。

 プログラムに現れない行番号にジャンプしようとしたとき。

 プログラムの最後の文を実行した後、そこからどの行にもジャンプしないとき。

TinyPowerのプログラムが与えられたとき、それが停まるかどうかを判定するプログラムを作成せよ。

Input

入力は以下の形式で与えられる。

N
stmt1
stmt2
:
stmtN

１行目にプログラムの行数 N (1 ≤ N ≤ 50) が与えられる。続く N 行に、TinyPowerプログラムの文 stmti が与えられる。stmti は、以下のいずれかの形式で与えられる。

line ADD var1 var2 var3

または

line ADD var1 var2 con

または

line SUB var1 var2 var3

または

line SUB var1 var2 con

または

line SET var1 var2

または

line SET var1 con

または

line IF var1 dest

または

line HALT

line, dest (1 ≤ line, dest ≤ 1000) は行番号、varj (英小文字１文字)は変数、con (0 ≤ con ≤ 15) は定数を表す。stmti 中の区切りは空白１文字とする。なお、プログラム中に変数は必ず１つ以上現れ、異なる変数名は５つまでしか現れないものとする。

Output

プログラムが停止するときは、プログラムに現れる変数の結果を、変数名の辞書順に改行区切りで出力し、停止しないときは「inf」を出力する。変数の結果は、変数名と変数の値を「=」で区切って出力する。

Sample Input 1

6
10 SET c 1
20 SET i 5
100 ADD s s i
110 SUB i i c
120 IF i 100
200 HALT

Sample Output 1

c=1
i=0
s=15

入力例１は、１から５までの整数の和を計算し、その結果を変数sに格納したあと、HALT文の実行で停止する。

Sample Input 2

3
10 SET c 1
120 IF c 10
20 HALT

Sample Output 2

inf

入力例２は、行番号10でcに1を代入し、次の行番号120のIF文で行番号10に戻ることを繰り返すので、停止しない。

Sample Input 3

3
111 SET c 1
12 SUB c c 2
777 SET a 4

Sample Output 3

a=0
c=1

入力例３は、行番号111でcに1を代入し、次の行番号12でcに-1を代入しようとするので、停止する。このときcの値は-1に更新されない。行番号777は実行されないので、aの値は初期値0のままである。



Sample input:
6
10 SET c 1
20 SET i 5
100 ADD s s i
110 SUB i i c
120 IF i 100
200 HALT


Sample output:
c=1
i=0
s=15

Submission status: Wrong Answer

Solution code:
n = int(input())
stmts = [input().split() for i in range(n)]

mapper = {}
for i, stmt in enumerate(stmts):
    mapper[stmt[0]] = i

vs = [None]*26
for stmt in stmts:
    for ope in stmt[2:]:
        if ope.isalpha():
            vs[ord(ope)-97] = 0
def check(x):
    return 0 <= x <= 16
def value(var):
    if var.isalpha():
        o = ord(var)-97
        return vs[o]
    return int(var)
def assign(var, x):
    o = ord(var)-97
    vs[o] = x

result = 1
state = set()
pc = 0
while pc < n:
    st = (pc, tuple(vs))
    if st in state:
        result = 0
        break
    state.add(st)
    stmt = stmts[pc]
    op = stmt[1]
    if op == 'ADD':
        v1, v2, v3 = stmt[2:]
        if not check(value(v2) + value(v3)):
            break
        assign(v1, value(v2) + value(v3))
        pc += 1
    elif op == 'SUB':
        v1, v2, v3 = stmt[2:]
        if not check(value(v2) - value(v3)):
            break
        assign(v1, value(v2) - value(v3))
        pc += 1
    elif op == 'SET':
        v1, v2 = stmt[2:]
        assign(v1, value(v2))
        pc += 1
    elif op == 'IF':
        v1, dest = stmt[2:]
        if value(v1):
            pc = mapper[dest]
        else:
            pc += 1
    else: # 'HALT'
        break
if result:
    for i in range(26):
        if vs[i] is not None:
            print("%c=%d" % (97+i, vs[i]))
else:
    print("inf")

Submission status: Wrong Answer

Solution code:
n = int(input())
stmts = [input().split() for i in range(n)]

mapper = {}
for i, stmt in enumerate(stmts):
    mapper[stmt[0]] = i

vs = [None]*26
for stmt in stmts:
    for ope in stmt[2:]:
        if ope.isalpha():
            vs[ord(ope)-97] = 0
def check(x):
    return 0 <= x <= 16
def value(var):
    if var.isalpha():
        o = ord(var)-97
        return vs[o]
    return int(var)
def assign(var, x):
    o = ord(var)-97
    vs[o] = x

result = 1
state = set()
pc = 0
while pc < n:
    st = (pc, tuple(vs))
    if st in state:
        result = 0
        break
    state.add(st)
    stmt = stmts[pc]
    op = stmt[1]
    if op == 'ADD':
        v1, v2, v3 = stmt[2:]
        if not check(value(v2) + value(v3)):
            break
        assign(v1, value(v2) + value(v3))
        pc += 1
    elif op == 'SUB':
        v1, v2, v3 = stmt[2:]
        if not check(value(v2) - value(v3)):
            break
        assign(v1, value(v2) - value(v3))
        pc += 1
    elif op == 'SET':
        v1, v2 = stmt[2:]
        assign(v1, value(v2))
        pc += 1
    elif op == 'IF':
        v1, dest = stmt[2:]
        if value(v1) > 0:
            if dest not in mapper:
                break
            pc = mapper[dest]
        else:
            pc += 1
    else: # 'HALT'
        break
if result:
    for i in range(26):
        if vs[i] is not None:
            print("%c=%d" % (97+i, vs[i]))
else:
    print("inf")

Submission status: Wrong Answer

Solution code:
n = int(input())
stmts = [input().split() for i in range(n)]

mapper = {}
for i, stmt in enumerate(stmts):
    mapper[stmt[0]] = i

vs = [None]*26
for stmt in stmts:
    for ope in stmt[2:]:
        if ope.isalpha():
            vs[ord(ope)-97] = 0
def check(x):
    return 0 <= x <= 16
def value(var):
    if var.isalpha():
        o = ord(var)-97
        return vs[o]
    return int(var)
def assign(var, x):
    o = ord(var)-97
    vs[o] = x

result = 1
state = set()
pc = 0
cnts = [0]*n
LIM = 15**5+10
while pc < n:
    cnts[pc] += 1
    if cnts[pc] > LIM:
        result = 0
        break
    stmt = stmts[pc]
    op = stmt[1]
    if op == 'ADD':
        v1, v2, v3 = stmt[2:]
        if not check(value(v2) + value(v3)):
            break
        assign(v1, value(v2) + value(v3))
        pc += 1
    elif op == 'SUB':
        v1, v2, v3 = stmt[2:]
        if not check(value(v2) - value(v3)):
            break
        assign(v1, value(v2) - value(v3))
        pc += 1
    elif op == 'SET':
        v1, v2 = stmt[2:]
        assign(v1, value(v2))
        pc += 1
    elif op == 'IF':
        v1, dest = stmt[2:]
        if value(v1) > 0:
            if dest not in mapper:
                break
            pc = mapper[dest]
        else:
            pc += 1
    else: # 'HALT'
        break
if result:
    for i in range(26):
        if vs[i] is not None:
            print("%c=%d" % (97+i, vs[i]))
else:
    print("inf")

Submission status: Wrong Answer

Solution code:
n = int(input())
stmts = [input().split() for i in range(n)]

mapper = {}
for i, stmt in enumerate(stmts):
    mapper[stmt[0]] = i

vs = [None]*26
for stmt in stmts:
    for ope in stmt[2:]:
        if ope.isalpha():
            vs[ord(ope)-97] = 0
def check(x):
    return 0 <= x <= 16
def value(var):
    if var.isalpha():
        o = ord(var)-97
        return vs[o]
    return int(var)
def assign(var, x):
    o = ord(var)-97
    vs[o] = x

result = 1
state = set()
pc = 0
cnts = [0]*n
LIM = 16**5+10
while pc < n:
    cnts[pc] += 1
    if cnts[pc] > LIM:
        result = 0
        break
    stmt = stmts[pc]
    op = stmt[1]
    if op == 'ADD':
        v1, v2, v3 = stmt[2:]
        if not check(value(v2) + value(v3)):
            break
        assign(v1, value(v2) + value(v3))
        pc += 1
    elif op == 'SUB':
        v1, v2, v3 = stmt[2:]
        if not check(value(v2) - value(v3)):
            break
        assign(v1, value(v2) - value(v3))
        pc += 1
    elif op == 'SET':
        v1, v2 = stmt[2:]
        assign(v1, value(v2))
        pc += 1
    elif op == 'IF':
        v1, dest = stmt[2:]
        if value(v1) > 0:
            if dest not in mapper:
                break
            pc = mapper[dest]
        else:
            pc += 1
    else: # 'HALT'
        break
if result:
    for i in range(26):
        if vs[i] is not None:
            print("%c=%d" % (97+i, vs[i]))
else:
    print("inf")

Submission status: Wrong Answer

Solution code:
n = int(input())
stmts = [input().split() for i in range(n)]

mapper = {}
for i, stmt in enumerate(stmts):
    mapper[stmt[0]] = i

vs = [None]*26
for stmt in stmts:
    for ope in stmt[2:]:
        if ope.isalpha():
            vs[ord(ope)-97] = 0
def check(x):
    return 0 <= x <= 16
def value(var):
    if var.isalpha():
        o = ord(var)-97
        return vs[o]
    return int(var)
def assign(var, x):
    o = ord(var)-97
    vs[o] = x

result = 1
state = set()
pc = 0
cnts = [0]*n
while pc < n:
    st = (pc, tuple(vs))
    if st in state:
        result = 0
        break
    state.add(st)
    stmt = stmts[pc]
    op = stmt[1]
    if op == 'ADD':
        v1, v2, v3 = stmt[2:]
        if not check(value(v2) + value(v3)):
            break
        assign(v1, value(v2) + value(v3))
        pc += 1
    elif op == 'SUB':
        v1, v2, v3 = stmt[2:]
        if not check(value(v2) - value(v3)):
            break
        assign(v1, value(v2) - value(v3))
        pc += 1
    elif op == 'SET':
        v1, v2 = stmt[2:]
        assign(v1, value(v2))
        pc += 1
    elif op == 'IF':
        v1, dest = stmt[2:]
        if value(v1) > 0:
            if dest not in mapper:
                break
            pc = mapper[dest]
        else:
            pc += 1
    elif op == 'HALT': # 'HALT'
        break
    else:
        exit(1)
if result:
    for i in range(26):
        if vs[i] is not None:
            print("%c=%d" % (97+i, vs[i]))
else:
    print("inf")

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
stmts = [input().split() for i in range(n)]

mapper = {}
for i, stmt in enumerate(stmts):
    mapper[stmt[0]] = i

vn = {}
for stmt in stmts:
    for ope in stmt[2:]:
        if ope.isalpha() and ope not in vn:
            vn[ope] = len(vn)
vs = [0]*len(vn)
def check(x):
    return 0 <= x < 16
def value(var):
    if var.isalpha():
        return vs[vn[var]]
    return int(var)
def assign(var, x):
    vs[vn[var]] = x

result = 1
state = set()
pc = 0
cnts = [0]*n
LIM = 16**5 + 10
while pc < n:
    cnts[pc] += 1
    if cnts[pc] > LIM:
        result = 0
        break
    stmt = stmts[pc]
    op = stmt[1]
    if op == 'ADD':
        v1, v2, v3 = stmt[2:]
        if not check(value(v2) + value(v3)):
            break
        assign(v1, value(v2) + value(v3))
        pc += 1
    elif op == 'SUB':
        v1, v2, v3 = stmt[2:]
        if not check(value(v2) - value(v3)):
            break
        assign(v1, value(v2) - value(v3))
        pc += 1
    elif op == 'SET':
        v1, v2 = stmt[2:]
        assign(v1, value(v2))
        pc += 1
    elif op == 'IF':
        v1, dest = stmt[2:]
        if value(v1) > 0:
            if dest not in mapper:
                break
            pc = mapper[dest]
        else:
            pc += 1
    elif op == 'HALT': # 'HALT'
        break
    else:
        assert 0
if result:
    for k in sorted(vn):
        print("%s=%d" % (k, vs[vn[k]]))
else:
    print("inf")

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
stmts = [input().split() for i in range(n)]

mapper = {}
for i, stmt in enumerate(stmts):
    mapper[stmt[0]] = i

vn = {}
for stmt in stmts:
    for ope in stmt[2:]:
        if ope.isalpha() and ope not in vn:
            vn[ope] = len(vn)
vs = [0]*len(vn)
def value(var):
    if var.isalpha():
        return vs[vn[var]]
    return int(var)
def assign(var, x):
    if not 0 <= x < 16:
        assert 0
    vs[vn[var]] = x

result = 1
state = set()
pc = 0
cnts = [0]*n
LIM = 16**len(vn) + 10
try:
    while 1:
        stmt = stmts[pc]
        cnts[pc] += 1
        if cnts[pc] > LIM:
            result = 0
            break
        op = stmt[1]
        if op == 'ADD':
            v1, v2, v3 = stmt[2:]
            assign(v1, value(v2) + value(v3))
            pc += 1
        elif op == 'SUB':
            v1, v2, v3 = stmt[2:]
            assign(v1, value(v2) - value(v3))
            pc += 1
        elif op == 'SET':
            v1, v2 = stmt[2:]
            assign(v1, value(v2))
            pc += 1
        elif op == 'IF':
            v1, dest = stmt[2:]
            if value(v1) > 0:
                pc = mapper[dest]
            else:
                pc += 1
        else: # 'HALT'
            break
except:...
if result:
    for k in sorted(vn):
        print("%s=%d" % (k, vs[vn[k]]))
else:
    print("inf")

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
stmts = [input().split() for i in range(n)]

mapper = {}
for i, stmt in enumerate(stmts):
    mapper[stmt[0]] = i

vn = {}
for stmt in stmts:
    for ope in stmt[2:]:
        if ope.isalpha() and ope not in vn:
            vn[ope] = len(vn)
vs = [0]*len(vn)
def value(var):
    if var.isalpha():
        return vs[vn[var]]
    return int(var)
def assign(var, x):
    if not 0 <= x < 16:
        assert 0
    vs[vn[var]] = x

def stmt_add(v1, v2, v3):
    def run(pc):
        assign(v1, value(v2) + value(v3))
        return pc+1
    return run
def stmt_sub(v1, v2, v3):
    def run(pc):
        assign(v1, value(v2) - value(v3))
        return pc+1
    return run
def stmt_set(v1, v2):
    def run(pc):
        assign(v1, value(v2))
        return pc+1
    return run
def stmt_if(v1, dest):
    def run(pc):
        if value(v1) > 0:
            return mapper[dest]
        else:
            return pc+1
    return run
def stmt_halt():
    def run(pc):
        return n
    return run
stmt_func = []
for i, stmt in enumerate(stmts):
    op = stmt[1]
    if op == 'ADD':
        stmt_func.append(stmt_add(*stmt[2:]))
    elif op == 'SUB':
        stmt_func.append(stmt_sub(*stmt[2:]))
    elif op == 'SET':
        stmt_func.append(stmt_set(*stmt[2:]))
    elif op == 'IF':
        stmt_func.append(stmt_if(*stmt[2:]))
    else:
        stmt_func.append(stmt_halt())

result = 1
state = set()
pc = 0
cnts = [0]*n
LIM = 16**len(vn) + 10
try:
    while 1:
        run = stmt_func[pc]
        cnts[pc] += 1
        if cnts[pc] > LIM:
            result = 0
            break
        pc = run(pc)
except:...
if result:
    for k in sorted(vn):
        print("%s=%d" % (k, vs[vn[k]]))
else:
    print("inf")

Submission status: Memory Limit Exceeded

Solution code:
n = int(input())
stmts = [input().split() for i in range(n)]

mapper = {}
for i, stmt in enumerate(stmts):
    mapper[stmt[0]] = i

vs = [None]*26
for stmt in stmts:
    for ope in stmt[2:]:
        if ope.isalpha():
            vs[ord(ope)-97] = 0
def check(x):
    return 0 <= x < 16
def value(var):
    if var.isalpha():
        o = ord(var)-97
        return vs[o]
    return int(var)
def assign(var, x):
    o = ord(var)-97
    vs[o] = x

result = 1
state = set()
pc = 0
cnts = [0]*n
while pc < n:
    st = (pc, tuple(vs))
    if st in state:
        result = 0
        break
    state.add(st)
    stmt = stmts[pc]
    op = stmt[1]
    if op == 'ADD':
        v1, v2, v3 = stmt[2:]
        if not check(value(v2) + value(v3)):
            break
        assign(v1, value(v2) + value(v3))
        pc += 1
    elif op == 'SUB':
        v1, v2, v3 = stmt[2:]
        if not check(value(v2) - value(v3)):
            break
        assign(v1, value(v2) - value(v3))
        pc += 1
    elif op == 'SET':
        v1, v2 = stmt[2:]
        assign(v1, value(v2))
        pc += 1
    elif op == 'IF':
        v1, dest = stmt[2:]
        if value(v1) > 0:
            if dest not in mapper:
                break
            pc = mapper[dest]
        else:
            pc += 1
    elif op == 'HALT': # 'HALT'
        break
    else:
        assert 0
if result:
    for i in range(26):
        if vs[i] is not None:
            print("%c=%d" % (97+i, vs[i]))
else:
    print("inf")

Submission status: Accepted

Solution code:
n = int(input())
stmts = [input().split() for i in range(n)]

mapper = {}
for i, stmt in enumerate(stmts):
    mapper[stmt[0]] = i

vn = {}
for stmt in stmts:
    for ope in stmt[2:]:
        if ope.isalpha() and ope not in vn:
            vn[ope] = len(vn)
vs = [0]*len(vn)
def stmt_add(v1, v2, v3):
    v1 = vn[v1]
    if v3.isdigit():
        v2 = vn[v2]
        const = int(v3)
        def run(pc):
            assert vs[v2] + const < 16
            vs[v1] = vs[v2] + const
            return pc+1
    else:
        v2 = vn[v2]
        v3 = vn[v3]
        def run(pc):
            assert vs[v2] + vs[v3] < 16
            vs[v1] = vs[v2] + vs[v3]
            return pc+1
    return run
def stmt_sub(v1, v2, v3):
    v1 = vn[v1]
    if v3.isdigit():
        v2 = vn[v2]
        const = int(v3)
        def run(pc):
            assert 0 <= vs[v2] - const
            vs[v1] = vs[v2] - const
            return pc+1
    else:
        v2 = vn[v2]
        v3 = vn[v3]
        def run(pc):
            assert 0 <= vs[v2] - vs[v3]
            vs[v1] = vs[v2] - vs[v3]
            return pc+1
    return run
def stmt_set(v1, v2):
    v1 = vn[v1]
    if v2.isdigit():
        v2 = int(v2)
        def run(pc):
            vs[v1] = v2
            return pc+1
    else:
        v2 = vn[v2]
        def run(pc):
            vs[v1] = vs[v2]
            return pc+1
    return run
def stmt_if(v1, dest):
    v1 = vn[v1]
    def run(pc):
        return mapper[dest] if vs[v1] else pc+1
    return run
def stmt_halt():
    def run(pc):
        return n
    return run
stmt_func = []
for i, stmt in enumerate(stmts):
    op = stmt[1]
    if op == 'ADD':
        stmt_func.append(stmt_add(*stmt[2:]))
    elif op == 'SUB':
        stmt_func.append(stmt_sub(*stmt[2:]))
    elif op == 'SET':
        stmt_func.append(stmt_set(*stmt[2:]))
    elif op == 'IF':
        stmt_func.append(stmt_if(*stmt[2:]))
    else:
        stmt_func.append(stmt_halt())

result = 1
pc = 0
cnts = [0]*n
LIM = 16**len(vn) + 10
try:
    while 1:
        run = stmt_func[pc]
        cnts[pc] += 1
        if cnts[pc] > LIM:
            result = 0
            break
        pc = run(pc)
except:...
if result:
    for k in sorted(vn):
        print("%s=%d" % (k, vs[vn[k]]))
else:
    print("inf")

Submission status: Accepted

Solution code:
def solve():
    from sys import stdin
    f_i = stdin
    
    N = int(f_i.readline())
    
    from string import ascii_lowercase
    next_line = {}
    S = {} # statements
    V = {} # values
    line = 0
    for i in range(N):
        stmt = f_i.readline().split()
        next_line[line] = stmt[0]
        line = stmt[0]
        op = stmt[1]
        if op == 'ADD' or op == 'SUB':
            v1, v2, v3 = stmt[2:]
            V[v1] = 0
            V[v2] = 0
            if v3 in ascii_lowercase:
                V[v3] = 0
            else:
                V[v3] = int(v3)
            S[line] = (op, v1, v2, v3)
        elif op == 'SET':
            v1, v2 = stmt[2:]
            V[v1] = 0
            if v2 in ascii_lowercase:
                V[v2] = 0
            else:
                V[v2] = int(v2)
            S[line] = (op, v1, v2)
        elif op == 'IF':
            v1, d = stmt[2:]
            V[v1] = 0
            S[line] = (op, v1, d)
        else:
            S[line] = (op,)
    next_line[line] = None
    
    v_num = 0
    for k in V:
        if k in ascii_lowercase:
            v_num += 1
    state_limit = len(S) * (16 ** v_num)
    
    nl = next_line[0]
    s = S[nl]
    cnt = 0
    while cnt < state_limit:
        cnt += 1
        op = s[0]
        if op == 'HALT':
            break
        elif op == 'ADD':
            v = V[s[2]] + V[s[3]]
            if v >= 16:
                break
            V[s[1]] = v
        elif op == 'SUB':
            v = V[s[2]] - V[s[3]]
            if v < 0:
                break
            V[s[1]] = v
        elif op == 'SET':
            V[s[1]] = V[s[2]]
        else:
            if V[s[1]]:
                nl = s[2]
                if nl in next_line:
                    s = S[nl]
                    continue
                else:
                    break
        nl = next_line[nl]
        if nl == None:
            break
        s = S[nl]
    
    if cnt == state_limit:
        print('inf')
    else:
        ans = []
        for k, v in V.items():
            if k in ascii_lowercase:
                ans.append(('{}={}'.format(k, v)))
        ans.sort()
        print('\n'.join(ans))

solve()

Submission status: Accepted

Solution code:
from itertools import product

def check():
  n = int(input())
  prog = [input().split() for _ in range(n)]
  
  v = set()
  for ss in prog:
    for s in ss:
      if "a" <= s <= "z":
        v.add(s)
  v = sorted(list(v))
  var_state = [0] * len(v)
  var_to_ind = dict(zip(v, range(len(v))))
  
  line_to_ind = {}
  for i, ss in enumerate(prog):
    line_to_ind[ss[0]] = i
  
  def fix(p):
    if p[1] == "ADD":
      if p[4] in var_to_ind:
        return [0, var_to_ind[p[2]], var_to_ind[p[3]], var_to_ind[p[4]]]
      else:
        return [1, var_to_ind[p[2]], var_to_ind[p[3]], int(p[4])]
    if p[1] == "SUB":
      if p[4] in var_to_ind:
        return [2, var_to_ind[p[2]], var_to_ind[p[3]], var_to_ind[p[4]]]
      else:
        return [3, var_to_ind[p[2]], var_to_ind[p[3]], int(p[4])]
    if p[1] == "SET":
      if p[3] in var_to_ind:
        return [4, var_to_ind[p[2]], var_to_ind[p[3]]]
      else:
        return [5, var_to_ind[p[2]], int(p[3])]
    if p[1] == "IF":
      if p[3] in line_to_ind:
        return [6, var_to_ind[p[2]], line_to_ind[p[3]]]
      else:
        return [6, var_to_ind[p[2]], 100]
    if p[1] == "HALT":
      return [7]
  
  prog = list(map(fix, prog))
  used = [[False] * n for _ in range(16 ** len(v))]
  xs = [1, 16, 256, 4096, 65536]

  ind = 0
  h = 0
  while True:
    if ind >= n:
      return True, v, var_state
    if used[h][ind]:
      return False, v, var_state
    used[h][ind] = True
  
    p = prog[ind]
    ins = p[0]
    
    if ins == 0:
      v1, v2, v3 = p[1:]
      temp = var_state[v2] + var_state[v3]
      if not temp < 16:
        return True, v, var_state
      h += (temp - var_state[v1]) * xs[v1]
      var_state[v1] = temp
    
    elif ins == 1:
      v1, v2 = p[1:3]
      con = p[3]
      temp = var_state[v2] + con
      if not temp < 16:
        return True, v, var_state
      h += (temp - var_state[v1]) * xs[v1]
      var_state[v1] = temp
    
    elif ins == 2:
      v1, v2, v3 = p[1:]
      temp = var_state[v2] - var_state[v3]
      if not 0 <= temp:
        return True, v, var_state
      h += (temp - var_state[v1]) * xs[v1]
      var_state[v1] = temp
    
    elif ins == 3:
      v1, v2 = p[1:3]
      con = p[3]
      temp = var_state[v2] - con
      if not 0 <= temp:
        return True, v, var_state
      h += (temp - var_state[v1]) * xs[v1]
      var_state[v1] = temp
    
    elif ins == 4:
      v1, v2 = p[1:]
      h += (var_state[v2] - var_state[v1]) * xs[v1]
      var_state[v1] = var_state[v2]
    
    elif ins == 5:
      v1 = p[1]
      con = p[2]
      h += (con - var_state[v1]) * xs[v1]
      var_state[v1] = con
    
    elif ins == 6:
      v1 = p[1]
      dest = p[2]
      if var_state[v1]:
        ind = dest - 1
  
    else:
      return True, v, var_state
  
    ind += 1

flag, v, var_state = check()
if flag:
  for t in zip(v, var_state):
    print(*t, sep="=")
else:
  print("inf")