P3952 [NOIP 2017 Senior] Time Complexity

NOIP 2017 Senior D1T2.

Xiao Ming is learning a new programming language, A++. After just learning loop statements, he excitedly wrote many programs and gave the time complexity he calculated for each. His programming teacher does not want to check them one by one, so here is your chance! Please write a program to judge whether the time complexity Xiao Ming gave for each program is correct. The loop structure in A++ is as follows: ```cpp F i x y loop body E ``` Here, `F i x y` means creating a new variable $i$ (the variable $i$ must not have the same name as any existing variable that has not been destroyed) and initializing it to $x$. Then compare $i$ with $y$: if $i$ is less than or equal to $y$, enter the loop; otherwise, do not enter. After each loop, $i$ is updated to $i+1$. Once $i$ becomes greater than $y$, the loop terminates. $x$ and $y$ can be positive integers (the relation between $x$ and $y$ is not fixed) or the variable $n$. The variable $n$ represents the problem size; in time complexity analysis, $n$ must be kept as a variable and not treated as a constant. It is much larger than $100$. `E` indicates the end of the loop body. When the loop body ends, the variables created by this loop are destroyed. Note: For convenience, this problem uses the uppercase letter $\operatorname O$ to denote the concept of $\Theta$ in the usual sense when describing complexity.

The first line of input contains a positive integer $t$, meaning there are $t$ ($t \le 10$) programs whose time complexity needs to be checked. For each program, we only need to extract the `F i x y` and `E` lines to compute the time complexity. Note: Loop structures can be nested. For each program, the first line contains a positive integer $L$ and a string. $L$ is the number of lines in the program, and the string denotes the program’s claimed complexity. `O(1)` means constant complexity, and `O(n^w)` means the complexity is $n^w$, where $w$ is a positive integer less than $100$. The input guarantees that the claimed complexity is only one of `O(1)` or `O(n^w)`. The next $L$ lines are either `F i x y` or `E`, representing the loop structure in the program. If a line starts with `F`, it indicates entering a loop, followed by three space-separated tokens `i x y`, where $i$ is a lowercase letter (guaranteed not to be $n$) representing the newly created variable name, and $x$ and $y$ may be positive integers or $n$. If they are positive integers, they are guaranteed to be less than $100$. If a line starts with `E`, it indicates the end of a loop body.

Output exactly $t$ lines, each corresponding to one program in the input. For each program, output `Yes`, `No`, or `ERR`. Output `Yes` if the actual complexity matches the given complexity; output `No` if it does not match; output `ERR` if there is a syntax error. The only syntax errors are: ① mismatched `F` and `E`; ② creating a variable with the same name as an already existing but not yet destroyed variable. Note: Even if a syntax error occurs inside a loop body that will never execute, it is still a compile-time error, and you must output `ERR`.

[Explanation of Sample 1] - The first program: $i$ goes from $1$ to $1$, which is constant complexity. - The second program: $x$ goes from $1$ to $n$, which is linear in $n$. - The third program: there is an `F` that starts a loop without a matching `E`, which is a syntax error. - The fourth program: two nested loops, so the complexity is $n^2$. - The fifth program: two separate single loops, so the complexity is linear in $n$. - The sixth program: the first loop is normal, but the second loop terminates immediately (because $n$ is much larger than $100$, and $100$ is larger than $4$). - The seventh program: the first loop cannot be entered, so it is constant complexity. - The eighth program: the variable $x$ in the second nested loop duplicates the variable from the first loop, which triggers syntax error ②, so output `ERR`. [Constraints and Notes] - For $30\%$ of the testdata: no syntax errors. It is guaranteed that the first $L/2$ lines are `F`-starting statements, and lines $L/2+1$ to $L$ are `E`-starting statements. $L \le 10$. If $x$ and $y$ are both integers, then $x < y$, and only $y$ may be $n$. - For $50\%$ of the testdata: no syntax errors. $L \le 100$. If $x$ and $y$ are both integers, then $x < y$, and only $y$ may be $n$. - For $70\%$ of the testdata: no syntax errors. $L \le 100$. - For $100\%$ of the testdata: $L \le 100$. --- If you need to hack, please private message @zhouyonglong or start a discussion, and provide testdata and an AC submission that this problem can be hacked by. Translated by ChatGPT 5