zoj 4049
Halting Problem
Time Limit: 1 Second Memory Limit: 65536 KB
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 8-bit register , 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 -th instruction.
Instruction | Description |
---|---|
add | Add to the register . As is a 8-bit register, this instruction actually calculates and stores the result into , i.e. . After that, go on to the -th instruction. |
beq | If the value of is equal to , jump to the -th instruction, otherwise go on to the -th instruction. |
bne | If the value of isn't equal to , jump to the -th instruction, otherwise go on to the -th instruction. |
blt | If the value of is strictly smaller than , jump to the -th instruction, otherwise go on to the -th instruction. |
bgt | If the value of is strictly larger than , jump to the -th instruction, otherwise go on to the -th instruction. |
A Dream Language program consisting of 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 -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.
Input
There are multiple test cases. The first line of the input is an integer , indicating the number of test cases. For each test case:
The first line contains an integer (), indicating the number of instructions in the following Dream Language program.
For the following lines, the -th line first contains a string (), indicating the type of the -th instruction of the program.
If equals to "add", an integer follows (), indicating the value added to the register;
Otherwise, two integers and follow (, ), indicating the condition value and the destination of the jump.
It's guaranteed that the sum of of all test cases will not exceed .
Output
For 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 Input
4
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 Output
Yes
Yes
No
No
Hint
For the second sample test case, note that is a 8-bit register, so after four "add 1" instructions the value of 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 will always be even, so it's impossible for the value of to be equal to 7, and the program will run forever.
Author: WENG, Caizhi
Source: The 2018 ACM-ICPC Asia Qingdao Regional Contest, Online
const int N =1e4+;
int vis[N][];
int t,n;
struct Ma{
char s[];
int v,k;
}ma[N];
void init()
{
for(int i=;i<=n;i++)
{
for(int j=;j<;j++){//一开始写成了26
vis[i][j]=;
}
}
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
init();
for(int i=;i<=n;i++)
{
scanf("%s",ma[i].s);
if(ma[i].s[]=='a') {
scanf("%d",&ma[i].v);
ma[i].k=;
}
else{
scanf("%d%d",&ma[i].v,&ma[i].k);
}
}
int pos=,ret=,flag=;
while()
{
if(pos==n+) {
flag=;
break;
}
if(vis[pos][ret]) {
flag=;
break;
}
vis[pos][ret]++;//由ret到第pos个指令,若重复出现就会死循环
if(ma[pos].s[]=='a') {
ret=(ret+ma[pos].v)%;
pos++;
}
else if(ma[pos].s[]=='e'){
if(ret==ma[pos].v){
pos=ma[pos].k;
}
else{
pos++;
}
}
else if(ma[pos].s[]=='n'){
if(ret!=ma[pos].v){
pos=ma[pos].k;
}
else{
pos++;
}
}
else if(ma[pos].s[]=='l'){
if(ret<ma[pos].v){
pos=ma[pos].k;
}
else{
pos++;
}
}
else if(ma[pos].s[]=='g'){
if(ret>ma[pos].v){
pos=ma[pos].k;
}
else{
pos++;
}
}
}
printf("%s\n",flag==?"Yes":"No");
}
return ;
}
最新文章
- Subsonic使用中
- 【原】webapp开发中兼容Android4.0以下版本的css hack
- ASM:《X86汇编语言-从实模式到保护模式》5-7章:汇编基础
- CMD魔法堂:获取进程路径和PID值的方法集
- 探索 OpenStack 之(15):oslo.messaging 和 Cinder 中 MessageQueue 消息的发送和接收
- Python之配置文件模块 ConfigParser
- Java内部类的自我理解
- 进位位(carry)与溢出位(overflow)的区别
- [LeetCode OJ] Candy
- 狗狗40题~(Volume A)
- java 简单的文件上传
- 查询最小未使用ID的SQL查询
- Primavera 6.0
- Minor GC、Major GC和Full GC之间的区别(转)
- 关于 Unchecked cast from Iterator to Iterator String 提示
- 各硬件设备在Linux中的文件名
- [转]tar 分包压缩与合并
- 【JAVA零基础入门系列】Day3 Java基本数据类型
- ●BZOJ 3126 [Usaco2013 Open]Photo
- Percona-Toolkit 之 pt-online-schema-change 总结