Halting Problem

Time Limit : 5 sec, Memory Limit : 262144 KB

プログラム停止判定

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

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

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 の値が0でないときだけ、行番号 dest にジャンプする
HALT プログラムを停止させる

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

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

  • HALT文を実行したとき。
  • 負の整数または16以上の整数を変数に代入しようとしたとき(変数の値は更新されない)。
  • プログラムに現れない行番号にジャンプしようとしたとき。
  • プログラムの最後の文を実行した後、そこからどの行にもジャンプしないとき。

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

Input

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

N
stmt1
stmt2
:
stmtN

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

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

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


Sample Input 2

3
10 SET c 1
120 IF c 10
20 HALT

Sample Output 2

inf

入力例2は、行番号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

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


Source: PC Koshien 2015 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2015-11-7
http://web-ext.u-aizu.ac.jp/pc-concours/