Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

Language:
The Halting Problem
 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 162 Accepted: 30

Description

The Halting Problem is a classic decision problem in computer science which basically requires to determine whether a given program will always stop (or terminate its execution) for an arbitrary given input or will execute infinitely. Alan Turing proved, in 1936, that it is impossible to solve the halting problem generalizing for any program-input pair. In this problem, however, given the description of a simple language, a program written in the language and an input for this program, you must determine whether the given program stops with the given input and, in the positive case, what output will be produced.

This language only works with integers from `0` to `999` (inclusive). In addition, the successor of `999` is `0`, and the predecessor of `0` is `999`. Moreover, it has ten variables (`R0` to `R9`), among which `R0` is always assigned the calling value of the program (that is, the input parameter) and `R9` is always assigned the exit (return) value. At the beginning of execution of the program, the value `0` is assigned to all these variables, with the exception of `R0`, which receives the input parameter.

The basic operations are assignment (`MOV`), addition (`ADD`), subtraction (`SUB`), multiplication (`MUL`), integer division (`DIV`) and remainder of integer division (`MOD`). All these operations have the syntax `COMMAND OPERAND1,OPERAND2` (without spaces between the comma and the operands), where `COMMAND` is one of these operations, `OPERAND1` is one of the 10 variables (`R0` to `R9`) and `OPERAND2` can be one of the 10 variables or an integer value (between `0` and `999`). All the operations modify the value of `OPERAND1`, consequently `MOV R4,100` is equivalent to assigning the value `100` to `R4`, while `MUL R3,R8` is equivalent to multiplying `R3` by `R8` and assigning the result to `R3`. The operation `DIV`, as well as `MOD`, returns `0` (zero) if `OPERAND2` is `0` or the equivalent variable has the value `0`. That is, `DIV R4,0` is equivalent to multiplying `MOV R4,0`. By integer division, we mean the integral part of the quotient of the division (without the fractional part). For example, the integer division of `7` by `2` is `3` (with remainder `1`).

There exist six decision flow commands: `IFEQ` (if equal), `IFNEQ` (if different), `IFG` (if greater), `IFL` (if less), `IFGE` (if greater or equal) and `IFLE` (if less or greater). The syntax of all of them is `COMMAND OPERAND1,OPERAND2` (without spaces between the comma and the operands), where both `OPERAND1` and `OPERAND2` can be variables (`R0` to `R9`) or integer values (between `0` and `999`). Thus, the command `IFEQ R4,123` is equivalent to testing whether `R4` is equal to `123`. When the tested condition is true, the program continues to execute normally the line subsequent to the decision command. When the condition is false, the program proceeds to execute the line subsequent to the nearest following `ENDIF`. All the decision commands must have a corresponding `ENDIF` command.

Finally, there exist the commands `CALL` and `RET`, both with the syntax `COMMAND OPERAND`, where `OPERAND` is a variable (`R0` to `R9`) or a direct value (between `0` and `999`). The command `CALL` calls the program recursively, passing `OPERAND` as the input parameter, that is, assigning the value of `OPERAND` to variable `R0`. And `RET` terminates the execution of the program, returning the value of `OPERAND` as the output result. The last line of the program will always be a command `RET`. It can be observed that, if the program calls itself through the command `CALL`, when execution returns, the value of `R9` is going to be changed with the value returned by the program. Note also that all the variables (`R0` to `R9`) are local, that is, a subsequent call to the program cannot change values saved in the variables of previous instance, with the exception of, naturally, the value of `R9`, which receives the return value of the called instance.

The following example illustrates a program that calculates the factorial of a number.

 line command 1 `IFEQ R0,0` 2 `RET 1` 3 `ENDIF` 4 `MOV R1,R0` 5 `SUB R1,1` 6 `CALL R1` 7 `MOV R2,R9` 8 `MUL R2,R0` 9 `RET R2`
• The 1st line: Check if the value of `R0` is `0`, if true, execute the next line; if not, jump to the 4th line (past the nearest following `ENDIF`).
• The 2nd line: Return `1` as the output of the program.
• The 3rd line: Mark the end of the decision block started at the first line.
• The 4th line: Assign the value of `R0` to `R1` (`R0 ← R1`).
• The 5th line: Subtract `1` from `R1` (`R0 ← R0 - 1`).
• The 6th line: Call the program passing `R1` as the input parameter.
• The 7th line: Save the value of `R9` (returned by the call before) in `R2` (`R2 ← R9`).
• The 8th line: Multiply the value of `R2` by `R0` (`R2 ← R2 * R0`).
• The 9th line: Return the value of `R2` as the output of the program.

The following table holds a resume of the commands for reference.

 command syntax meaning `MOV` `MOV OP1,OP2` `OP1 ← OP2` `ADD` `ADD OP1,OP2` `OP1 ← OP1 + OP2` `SUB` `SUB OP1,OP2` `OP1 ← OP1 - OP2` `MUL` `MUL OP1,OP2` `OP1 ← OP1 * OP2` `DIV` `DIV OP1,OP2` `OP1 ← OP1 / OP2` `MOD` `MOD OP1,OP2` `OP1 ← OP1 % OP2` `IFEQ` `IFEQ OP1,OP2` `IF OP1 == OP2` `IFNEQ` `IFNEQ OP1,OP2` `IF OP1 != OP2` `IFG` `IFG OP1,OP2` `IF OP1 > OP2` `IFL` `IFL OP1,OP2` `IF OP1 < OP2` `IFGE` `IFGE OP1,OP2` `IF OP1 >= OP2` `IFLE` `IFLE OP1,OP2` `IF OP1 <= OP2` `ENDIF` `ENDIF` Mark the end of a conditional execution block `CALL` `CALL OP` Call the program will `OP` as input `RET` `RET OP` `return OP`

Input

The input contains several test cases. Each test case starts with two integers, L and N, representing respectively the number of lines of the program (1 ≤ L ≤ 100) and the value of the input parameter of the program (0 ≤ N < 1000). The following L lines contain the program. It can be assumed that it is always syntactically correct in accordance with the rules defined above. All the commands (as well as the variables) only contain capital letters. The end of the input is marked by a case where L = N = 0 which should not be processed.

Output

For each test case, your program should produce one line containing an integer which represents the exit (return) value for the given input N, or an asterisk (*) in the case that the program never terminates.

Sample Input

```9 6
IFEQ R0,0
RET 1
ENDIF
MOV R1,R0
SUB R1,1
CALL R1
MOV R2,R9
MUL R2,R0
RET R2
2 123
CALL R0
RET R0
0 0```

Sample Output

```720
*```

Source

South America 2006, Brazil Subregion

[Submit]   [Go Back]   [Status]   [Discuss]