
ZOJ Problem Set  4049
In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program, whether the program will finish running (i.e., halt) or continue to run forever. Alan Turing proved in 1936 that a general algorithm to solve the halting problem cannot exist, but DreamGrid, our beloved algorithm scientist, declares that he has just found a solution to the halting problem in a specific programming language  the Dream Language! Dream Language is a programming language consists of only 5 types of instructions. All these instructions will read from or write to a 8bit register $r$, whose value is initially set to 0. We now present the 5 types of instructions in the following table. Note that we denote the current instruction as the $i$th instruction.
A Dream Language program consisting of $n$ instructions will always start executing from the 1st instruction, and will only halt (that is to say, stop executing) when the program tries to go on to the $(n + 1)$th instruction. As DreamGrid's assistant, in order to help him win the Turing Award, you are asked to write a program to determine whether a given Dream Language program will eventually halt or not. InputThere are multiple test cases. The first line of the input is an integer $T$, indicating the number of test cases. For each test case: The first line contains an integer $n$ ($1 \le n \le 10^4$), indicating the number of instructions in the following Dream Language program. For the following $n$ lines, the $i$th line first contains a string $s$ ($s \in \{\text{"add"}, \text{"beq"}, \text{"bne"}, \text{"blt"}, \text{"bgt"}\}$), indicating the type of the $i$th instruction of the program.
It's guaranteed that the sum of $n$ of all test cases will not exceed $10^5$. OutputFor each test case output one line. If the program will eventually halt, output "Yes" (without quotes); If the program will continue to run forever, output "No" (without quotes). Sample Input4 2 add 1 blt 5 1 3 add 252 add 1 bgt 252 2 2 add 2 bne 7 1 3 add 1 bne 252 1 beq 252 1 Sample OutputYes Yes No No HintFor the second sample test case, note that $r$ is a 8bit register, so after four "add 1" instructions the value of $r$ will change from 252 to 0, and the program will halt. For the third sample test case, it's easy to discover that the value of $r$ will always be even, so it's impossible for the value of $r$ to be equal to 7, and the program will run forever. Author: WENG, Caizhi Source: The 2018 ACMICPC Asia Qingdao Regional Contest, Online 