0851 - プログラム停止判定

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

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

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のプログラムが与えられたとき、それが停まるかどうかを判定するプログラムを作成せよ。

入力

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

N
stmt1
stmt2
:
stmtN

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

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) は行番号、var_j (英小文字１文字)は変数、con (0 ≤ con ≤ 15) は定数を表す。stmt_i 中の区切りは空白１文字とする。なお、プログラム中に変数は必ず１つ以上現れ、異なる変数名は５つまでしか現れないものとする。

出力

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

入力例 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

出力例 1

c=1
i=0
s=15

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

入力例 2

3
10 SET c 1
120 IF c 10
20 HALT

出力例 2

inf

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

入力例 3

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

出力例 3

a=0
c=1

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