P9931 [NFLSPC #6] Challenge the Halting Problem

As an OIer/XCPCer in the new era, you are no longer satisfied with challenging NP-complete problems. You want to challenge the undecidability in mathematics—the Turing halting problem.

Turing gives you a program. At the very beginning of the program, there is one and only one variable $A$, with initial value $0$. The program has $n$ lines, numbered $1 \sim n$. Each line is one of the following forms: - `A a`: Set $A \gets A + a$, then execute the next line. - `G x`: Execute line $x$. - `I l r x y`: If $A \in [l, r]$, execute line $x$; otherwise, execute line $y$. - `E`: Terminate the program immediately. It is guaranteed that the last line is `E`. Turing wants you to determine whether this program will terminate when executed starting from line 1. To further test whether you can really decide the halting problem (or you are just pretending?), Turing also requires you to output the final value of $A$. If the program does not terminate and there does not exist a moment after which $A$ no longer changes, output `@Turing ?`.

This problem contains multiple test cases. The first line contains a positive integer $T$ indicating the number of test cases. For each test case: - The first line contains an integer $n$, indicating the number of lines in the program. - The next $n$ lines describe the program.

For each test case, output two lines: - The first line outputs a string `Yes` or `No`, indicating whether the program will terminate. - The second line outputs an integer $A_{0}$ or the string `@Turing ?`, indicating the final value of $A$.

For all testdata, $1 \leq T \leq 1000$, $1 \leq n, \sum n \leq 10^5$, $1 \leq a \leq 10^9$, $0 \leq l \leq r \leq 10^9$, $1 \leq x, y \leq n$. It is guaranteed that all numbers in the input are integers. - Subtask 1 (15 points): There are no `I` statements. - Subtask 2 (20 points): $r \leq 100$. - Subtask 3 (40 points): $\sum \max r \leq 10^5$. - Subtask 4 (25 points): No special constraints. Source: NFLSPC #6 G by chenxia25 Translated by ChatGPT 5